Syureu

찍먹을 좋아하는 사람.

STL VS COLLECTION Series 1. TreeMap

6 분 소요

Map

맵은 Key:Value 쌍을 가진 자료구조이다. 위키피디아에서는 Associative Array(연관 배열)이라고 부르며 뭐 연관배열, 맵, 딕셔너리(아마 파이썬도 이 이름) 등등으로 불린다.
다음과 같은 특징을 가진다.

  • Key는 중복 될 수 없다.
  • Value는 중복 되던가 말던가
  • 순서는 구현에 따라 가질 수도 없을 수도 있다.

맵의 사용 용도

JavaScript의 경우 Object이 이러한 형태이기에 js 유저들은 아주 익숙하지만 딱히 자료구조를 접해본 적이 없는 c, java 유저들은 이걸 어떤 형태로 쓸까 잘 모를 수 있다.

예를 들어 다음과 같은 상황을 가정해 보자. 학생 3명의 영어 점수를 저장한다. 그냥 배열과 같은 자료로 나타낼 경우

int english_score[3];
english_score[0] = 100;
english_score[1] = 75;
english_score[2] = 80;

학생의 이름은 각각 (담담, 훈훈, 팡팡) 이라고 하자.
우리는 이 소스를 작성한 사람이라 각각의 점수가(즉 몇 번째 칸이) 누구의 점수인지 알 수 있다. 하지만 그렇지 않은 경우에 이게 누구 점수 인지를 간접적으로 나타내어야 한다.

struct score{
    string name;
    int score;
};

score english_score[3];

english_score[0].name = "담담";
english_score[0].score = 100;
english_score[1].name = "훈훈";
english_score[1].score = 75;
english_score[2].name = "팡팡";
english_score[2].score = 80;

와 같이 구조체를 사용하거나, 강타입이 아닌 언어 혹은 배열에 여러타입을 섞을 수 있는 경우에서는 [2][3] 배열을 만들고 같은 행의 0번 열은 이름, 1번 열은 점수.. 와 같은식으로 나타낼 것이다.

맵을 사용한다면?

맵을 사용한다면 위와 같은 상황을 다음과 같이 표현 할 수 있게 된다.

#include<map>
using namespace std;

map<string,int> mymap;

mymap.insert({"담담", 100});
mymap["훈훈"] = 75;
if (mymap.find("팡팡") == mymap.end()) {
    mymap.insert({"팡팡", 80});
}

cout << mymap["훈훈"];

Output : 75

맵을 사용하지 않았을 경우 해당 변수의 의미를 설계적으로 들고 있거나 아니면

int eng_score_damdam = 100;

과 같은 재사용이 구데기인 방법을 이용했어야 할 것을 맵을 통해 표현 가능해진다.
소스를 조금 설명해 보자면 기본적으로 맵에 데이터를 넣는 것은 map 객체의 insert()함수이다.
이 함수는 std::pair 를 파라메터로 받을 수 있게 오버라이딩 되어 있다.

근데 맵이 아니어도 할 수는 있잖아?

위의 서사는 사실 아래의 것을 설명하기 위한 주저리였다. 다음과 같은 상황도 가정해보자.

이름이 팡팡인 사람의 영어 점수는 얼마인가?


일반적인 배열을 사용한 경우 다음과 같이 찾을 것이다.

for(int i=0; i<3; ++i) {
    if(english_score[i].name == "팡팡") {
        cout << english_score[i].score;
    }
}

Output : 80

팡팡이의 점수를 찾기 위해 우리는 배열 전체를 순회했다. 이 배열은 원소가 3개밖에 없어서 아주 다행스럽게 시간이 얼마 걸리지 않는다. 그럼 다음과 같은 상황에는 어떨까?

사실 배열에는 10만명의 영어 점수가 있다. 그리고 너는 우리가 주는 사람 이름 목록을 출력해야되는데 이 목록도 10만개가 있다. 코드를 짤때는 모르겠지만 우리는 팡팡이의 점수를 10만번 물어볼거고, 또 팡팡이는 99999번째 인덱스에 있단다 헤헤

for문 순회의 범위만 <100000 으로 조정하고 돌려도 우리는 이름 목록을 다 출력하는데 애략 10만*10만 을 순회해야한다. 100억번의 연산이고 ps에서 대충 1초에 1억번의 연산량을 간이 시간복잡도의 척도로 삼으니 우리는 100초에 걸려 문제를 해결하는 방법을 사용한 것이다.

맵을 사용 한다면?

TreeMap 은 말그대로 Tree로 만들어진 Map이다. 보통의 경우 이진 트리 구조이기 때문에 삽입, 검색, 삭제에 O(logN)의 시간이 든다. 자료구조를 다루는 포스트가 아니기 때문에 이진트리가 뭔지 모른다면 구글에게 물어 보도록

다시 같은 질문을 보자.

사실 배열에는 10만명의 영어 점수가 있다. 그리고 너는 우리가 주는 사람 이름 목록을 출력해야되는데 이 목록도 10만개가 있다. 코드를 짤때는 모르겠지만 우리는 팡팡이의 점수를 10만번 물어볼거고, 또 팡팡이는 99999번째 인덱스에 있단다 헤헤헤

트리로 구현된 맵(앞으로 다시 맵으로 줄여 부르겠음)을 사용할 경우 검색에도 logN의 시간밖에 들지 않는다. 그래서 위와 같은 문제에 최악의 경우 10만*log2(10만)번의 연산량이 소모되므로 약 167만회의 연산만에 해결이 가능하다.

C++에서의 Map

C++에서 맵은 헤더 #inlcude<map>, 이름공간 std::map에 있다.
sBBST의 한 종류인 Red-Black 트리로 구현되어 있다. 마찬가지로 레드블랙 트리가 궁금하다면 구글로 ㄱㄱ!
또 맵에 대한 모든 멤버를 알고싶다면 이것도 따로 찾아보길.. 아마 이 시리즈의 내용은 다 이런식일 것이다. 그렇다면 내가 ps하면서 주요하게 썼던 멤버와 사용법등을 알아보자.

Map 객체 선언

map<key-type, value-type> object_name;

키타입과 밸류타입은 내가 쓰고싶은대로 정한다. 이름, 점수를 나타내고 싶으면

map<string, int>m;

과 같이하면 된다.

데이터 삽입

map.insert({key, value});

map<string,int>m; 으로 선언되었다면

m.insert({"담담", 100});

과 같이.
pair형을 받는 오버로딩된 insert가 있다. c++11부터 지원하는 initializer list를 이용해 편하게 넣을 수 있다. c++98의 환경이라면 직접

m.insert(make_pair(key, value));

와 같이 적어줘야 할 것이다.

당연하게도 key 와 value는 선언된 맵 객체의 형을 따라가야 한다. 맵은 키 중복이 안되기 때문에 위와 같이 insert를 사용해서 넣는 경우 이미 해당 키로 된 데이터가 있으면 삽입되지않는다.

추가 된 부분

놀랍게도 컬렉션은 모든 함수가 자기 동작 전의 상태에 관한 반환이 있는 것을 보고 c++은 어떨까 찾아봤는데 놀랍게도 있다.

insert함수의 경우 pair쌍을 반환하는데 first는 이터레이터이며, 성공적으로 반환시 삽입한 애의 이터레이터, 실패시(이미 해당 키가 있으면) 그 키가 있는 데이터의 이터레이터이고, second는 성공여부이다. 즉 성공시 true 실패시 false

데이터 검색

map.find(key)

iterator를 반환한다. 없으면 end iterator를 내뱉는다. 즉 위에 팡팡이를 넣을때 처럼 이 맵에 있는지 없는지 검사할 때는

if (m.find(key) == m.end()) {
    // 없을 때 할 작업
}

를 통해 알 수 있다. 문제에 따라 없을때 그냥 바로 넣는게 아니라 따로 카운팅 한다던지 뭔가 처리를 해줘야 할 때 이렇게 쓰면 된다. 위의 예제는 꼭 그런건 아니었지만.

그리고 이터레이터를 반환하기 때문에 it->first 로 key를, second로 value를 접근 할 수 있다. 내부에 pair가 있는 것을 여기서도 볼 수 있다.

데이터 변경

map[key] = value;

놀랍ㄱ베도 c++에서 변경을 설명할 때 삽입과 검색을 같이 실행할 수 있다. 위에 비하면 진짜 말도안되게 개꿀임; 그리고 insert 되지 않은 상태에도(해당 키로 된 데이터가 없어도) 바로 만들어주고 처리한다. 즉 위에서 훈훈이라는 키로 된 데이터를 insert 한 적 없지만 저렇게 []로 접근한 순간 해당 데이터를 만들어준다. value는 각 데이터의 초기값으로 초기화 된다. (int는 0, string은 “” 등)

즉

map[key] = value;

key가 없을 때 이 문장의 뜻을 보면 map객체에서 key가 key인 항목을 찾아라. 근데 없었기 때문에 m.insert({key, 0}); 과 같은 로직이 수행되고, 이후 map.find(key)->second = value; 와 같이 된것이다.

위까지 다 삽입과 검색 등등에 관한거고 변경도 개꿀스럽게

cout << ++m["담담"] << '\n';
cout << m["담담"] *= 10;

Output : 101
1010

이런게 된다는 말이다.

물론 고생스럽게 다음과 같이 해도 된다.

auto it = m.find("담담");
it->second++;
m.find("담담")->second *= 10;

데이터 삭제

map.erase(key);

too 심플. key에 해당하는 데이터 삭제

m.erase("담담");

추가 된 부분

insert와 마찬가지로 erase도 반환해준다. 우리가 쓴 erase의 경우 키로 삭제하는 거라 삭제된 갯수를 반환해준다. 즉 성공여부와 동치라 봐도 될듯

Java에서의 Map

놀랍게도 post를 쓸 때까지 Java에서 Map 딱한번 써봄; 심지어 그것도 HashMap이니… 이포스트를 쓰면서 TreeMap은 처음 써보는 것이다.

Java에서의 맵 컬렉션은
import java.util.Map; (인터페이스)
import java.util.TreeMap; (클래스)
에 있다.

마찬가지로 레드블랙트리 기반.

트리맵의 경우 최악에 logN을 보장해주기 위해 AVL계열의 트리 구현체를 사용하는데 레드블랙트리가 실성능이 훨 나은가보다.

Map 객체 선언

Map<key-type, value-type> objectName = new TreeMap<>();

같은 예제의 경우

Map<String, Integer> m = new TreeMap<>();

데이터 삽입

map.put(key, value);

뭐 평범한 삽입인데, 이전 value를 뿌려준다. 없으면 null 리턴 역시 같은 예제로

System.out.println(m.put("담담", 100));
System.out.println(m.put("담담", 100));

Output : null
100

데이터 검색

map.get(key);

이터레이터를 내뱉는 c++과 다르게 value타입을 바로 뿌려준다.

System.out.println(m.get("담담"));

Output : 100

데이터 변경

map.replace(key, value);

map.replace(key, oldValue, newValue);

위의 것은 그냥 바꿔버리면서 리턴으로 바뀌기 전의 값을 준다. 아래는 key와 oldValue가 맞으면, newValue로 준다. 리턴은 성공여부인 부울린

int tmp = m.get("담담");
System.out.println(m.replace("담담", ++tmp));
tmp = m.get("담담");
System.out.println(m.replace("담담", tmp, tmp*10));
System.out.println(m.get("담담"));

Output : 100
101
1010

이 시리즈를 괜히 쓰기 시작했다는 생각이 든다.

데이터 삭제

map.remove(key);

map.remove(key, value);

여러 종류가 있는데 전자는 키만 맞으면 삭제한다. 리턴은 삭제되기 전 들고 있던 값. 후자는 키, 밸류가 맞는 데이터를 삭제하고 리턴은 역시 성공여부 부울린이다.

System.out.println(m.remove("땅땅"));
System.out.println(m.remove("담담", 50));
System.out.println(m.remove("담담", 1010));

Output : null
false
true

실전

솔브드 태그는 링크로 마련했다. 난이도 순으로 정렬시 대충 실4 부터 출발하는데, 맵 입문용 ~ 간단한 문제는 거의 TreeMap이나 HashMap의 사용처를 구분하지 않아도 풀 수 있다. 한 문제는 c++로 한문제는 자바로 풀어봐야겠다.

BOJ 1620 나는야 포켓몬 마스터 이다솜 (https://www.acmicpc.net/problem/1620)

풀이 보러가기

마치며

다음 내용은 아마 HashMap일거에요. TreeMap만 있을땐 최대한 HashMap과의 비교 등등은 적지 않고 했고, HashMap일때 이에 대해 같이 얘기할 기회가 있을 겁니다. 이후 Set을 하고 MultiMap 같은걸 다룰 수 있나 공부하고 된다면 포스트 할 것 같네요.

참고