set 과 multiset 그리고 map과 multimap 그리고 unordered_map

개요

지금까지 수많은 코딩테스트 문제를 풀어왔고, 꾸준히 그렇게 하려고 매일 적어도 2개 이상의 프로그래머스 lv.3~lv4를 풀려고 노력한다. 정말 풀리지 않을 때는 힌트를 참고하고, 이에 대해서 찾아본 후 블로그에 포스팅된 글을 보고 이해하려 한다. 답을 보고 푼 문제인 경우는 따로 메모해두었다가 다음 날 답을 보지 않고 스스로 풀어내려 한다. 이 과정에서 적절한 자료구조를 활용하면 금방 풀릴 것 같은 문제인데 지식의 한계로 그러지 못했던 문제에서 multiset이라는 좋은 것이 있어서 정리하려 한다.

참고로 이 문제는 아래 링크로 남기겠다.

https://school.programmers.co.kr/learn/courses/30/lessons/42628#

서론

문제를 보고 처음에는 제목 그대로 우선순위큐를 두 개를 써서 접근하였다. 내림차순과 오름차순으로 정리되는 우선순위 큐를 만든 후에 최댓값을 지울 때는 내림차순 우선순위큐에서, 최솟값을 지울 때는 오름차순 우선순위큐에서 값을 지웠다. 리턴값으로 최솟값과 최댓값을 반환해야 하는데 사실 최댓값이든 최솟값이든 값을 지우면 두 개 모두의 우선순위큐에서 해당 값을 지워주어야 논리적 오류가 발생하지 않는다. 하지만 우선순위큐에서는 top값만을 pop 할 수 있기 때문에 큐에 가장 뒤에 부분에는 접근하지 못한다.

이에 앞 뒤로 모두 접근 가능한 deque를 사용하려 했지만 vector와 마찬가지로 자동으로 sort 되지 않기 때문에 값을 넣을 때마다 sort 하기에는 시간복잡도에서 너무 비효율적일듯했다. 이에 중복된 수가 나오지 않는다는 가정하에 우선순위큐 하나와 map을 활용해서 큐에 넣어졌다가 pop 된 수는 map에 표시해놓고 반환할 때 이 값들은 제외한 후 값을 반환하는 방법을 쓰려했으나, 이 방법도 고려해야 할 조건이 많았고 복잡해졌다.

다른 언어에서는 어떨지 모르겠으나, 분명히 자동으로 정렬을 해주면서 앞 뒤로 접근이 가능한 자료구조가 있을 것 같았다. 그렇게 찾아보던 와중 multiset이라는 자료구조를 보았다. 평소에 set이라는 자료구조는 정말 잘 들어맞는 문제를 제외하고는 거의 쓴 적이 없다. 더군다나 multiset이라는 자료구조는 어디선가 본 적은 있지만 실제 코딩테스트에서 쓴 적은 없는듯했다. 이 기회에 set과 multiset을 잘 정리하여 앞으로 이 문제와 비슷한 문제를 맞닥뜨렸을 때 이 자료구조가 내 머릿속에서 잘 떠오를 수 있길 바란다. 

본론

set

<set> header file에 있다.

균형 이진트리로 구현되어 있다.

 

연관 컨테이너이다.

연관 컨테이너란? key와 value를 통해 관계있는 값을 묶어서 저장하는 컨테이너이다.

연관컨테이너 특)

-노드기반컨테이너

-균형 이진트리

-멤버 변수 생성자 등이 매우 비슷함

 

key만 가지고 있는 연관컨테이너이다.

begin, end, rbegin, rend iterator로 접근 가능하다.

insert()로 삽입가능하고, 삽입시에 자동으로 정렬된 위치에 삽입된다.

find(k)로 k가 가리키는 반복자를 반환한다.

erase(iter)로 iter에 해당하는 값을 지울 수 있다.

key값으로 중복이 허용되지 않기에 중복된 값을 삽입하면 수가 늘어나지 않고 그대로다. 

 

여기에서 multiset은 set과 거의 모든 부분이 같지만 key값이 중복될 수 있다는 점이 다르다.

lower_bound(k) k가 시작되는 구간의 반복자 반환 [] 닫힌 구간, a, b, c, k, k, z -> k

upper_bound(k) k가 끝나는 구간의 반복자 반환 () 열린 구간 a,b,c,k,k,z -> z

equal_range(k) {lower_bound(k), upper_bound(k)} 

equal_range(k). first, equal_range(k). second처럼 접근 가능

 

map

< map > header file에 있다.

Red-Black Tree 라는 균형 이진트리로 구현되어 있다.

 

연관 컨테이너이다.

 

key와 value를 가지고 있는 연관컨테이너이다.

key에 따라서 자동으로 정렬된다.

set과 매우 비슷한 특징을 가진다.

하나의 key만을 가진다(중복된 key를 가질 수 없다)

 

multimap

중복된 key를 가질 수 있다.

key의 값에 따라 자동으로 오름차순으로 정렬된다.

같은 key의 값이 들어오면 들어온 순서대로 들어온다.(value의 값에 따라 재정렬되지 않는다) (value의 값이 앞선 값보다 크든 작든 같든 상관없이 순서대로 들어온다.

 

unordered_map

key와 value로 저장된다.

unordered_map은 트리가 아닌 해쉬맵으로 구현된다. 따라서 자동으로 정렬되지 않는다. 이에 정렬될때 시간복잡도를 줄일수 있다. 따라서 정렬이 필요하지 않을때에 쓰면 효율적일 수 있다. 그러나 같은 key가 반복 되어서 들어온다면 해쉬충돌이 일어나서 최악의 복잡도가 O(N)까지 나올 수 있으므로 key가 많이 중복 되는 상황에서는 효율이 오히려 더 좋지 않다.

결론

이 처럼 질문에 반복되는 숫자가 나오지 않는다는 명시적인 문장이 없기 때문에, 중복을 허용하면서도 자동으로 key값에 의해 정렬이 되는 multiset을 활용함으로써 삽입시 삭제 시 O(logN)의 복잡도로 구현 가능했다.

간단하게 값을 넣을 때는 multiset에 insert 해주고 최솟값을 제거해야 할 때는 가장 앞부분을 지워주고 최댓값을 지워줄 때는 가장 뒷부분을 지워주었다. 

이때 iterator로 접근하여 지워주어야 하는데 약간의 주의가 필요하다.

multiset s;

최솟값을 지울 때는

s.erase(s.begin());

이런 식으로 지울 수 있지만 최댓값을 지울 때는

s.erase(s.end());

이런 식으로 지울 수 없다. s.end()는 iter의 한 칸 뒤의 값을 가리키기 때문에

s.erase(prev(s.end())); 라든가 s.erase(--s.end()))라는 식으로 한 칸 앞으로 옮겨준 부분을 지워줘야 하는 점을 주의하자!

 

마무리

익숙하지 않은 container도 평소에 많이 써봄으로써 생각하는 길을 여러 개 뚫어 놓자

 

위의 내용을 바탕으로 개발자 면접 간

1. set과 multiset이 어떤 것일까요?

2. 각각은 어떤 곳에서 쓰이나요?

3.map과 unordered_map은 무엇인가요?

4. map과 unordered_map은 각각 어떤 상황에서 쓰이나요?

 

등에 대한 질문을 생각해 볼 수 있겠다. 스스로에게 질문을 해보고 답해보자.

 

헷갈리는 부분은 보완하기! 찡긋 O.<

 

틀린 부분이나 보완해줬으면 하는 내용이 있으면 댓글로 알려주세요! 추가 설명이 필요하신 부분도 댓글로 알려주세요.

어떠한 피드백도 환영입니다. 긴 글 읽어주셔서 감사합니다.