백준 1620번 풀면서 c++ map

백준 1620번 문제를 풀면서

1.map<int, string> 와 2.map<string, int> 으로 고민을했다.

1번의 경우는 번호순으로 정렬하되, value -> key 작업에서 주어진 string과 같은 value를 찾아서 key를 출력해야된다.

2번의 경우는 문자열순으로 정렬하되, value -> key 작업에서 따로 string 배열을 만들어 O(1)으로 참조가 가능했다.

 

key를 문자열로 정렬하는것은 int에 비해 느릴것이고 같은 key를 찾는것도 느릴것이라 생각해서 

1번을 택했었다. 하지만 1번의 경우는 시간초과고 2번은 180ms 정도로 성공했다.

 

지금 글을 쓰면서 생각해보니 당연한거같네..

1번의 경우 value->key 작업에서 번호에 대해서만 정렬되있어서 찾는데 오래걸릴거고.. 각 비교또한 O(L) 일테니..

그에반해 2번은 value->key는 O(1)이고 key->value 부분은 정렬되어있어서 O(nlog(n)). 아예 차이나네;;

 

뭔가 바보같았지만;;

암튼 map 만들땐 어떤게 정렬되는게 편한지.. 그에따라서 key로 설정하자.