c++ map = 연산자와 swap 메서드에 대해 알아봅시다.

 제가 낸 3회 코딩테스트 문제 중에 가희와 쓰레기 놀이가 있었습니다. 이 문제의 input에 대한 output 파일을 생성하기 위해 작성한 파일이 이 코드였는데요. 생각보다 오래 걸렸답니다. 대략 13 ~ 14초 정도 걸렸던 걸로 기억해요. 이 로직을 그대로 validator에도 썼기 때문에, 벨리 데이터가 시간 초과가 나기도 했습니다.

 

 제가 작성했던 처음 버전의 솔루션 코드를 유심히 보실 필요는 있습니다. 왜냐하면, 생각보다 비효율적인 일을 하고 있기 때문입니다.

 

 

---

 이 부분을 먼저 보겠습니다. new_ref의 내용을 그대로 ref에, new_con의 내용을 그대로 con에 넣어버리는 부분입니다. bfs 함수가 끝나기 직전에 호출하는데요. 이 두 친구는 bfs 내의 지역 변수로 선언되어 있어요.

 

 

 이 부분입니다. bfs 함수가 끝나기 직전에 ref = new_ref와 con = new_con이 호출됩니다. 이 이야기는 저 부분이 호출되고 나서, new_ref와 new_con은 더 이상 쓰지 않는다는 의미와 같습니다. = 연산자 때문에 어떤 일이 일어나는지 간단하게 알아보도록 할게요.

 

 

 먼저 균형 트리가 이렇게 있어요. 이것을 복사할 거에요. 어떻게 하면 될까요? 먼저 1을 복사합니다.

 

 

 그러면 요래 될 겁니다. 이제 1의 왼쪽에 있는 것들을 모두 복사할 거에요.

 

 

 복사가 되었습니다. 이제 남은 것은 1의 오른쪽에 있는, R입니다.

 

 

 재귀적으로 복사만 하면 됩니다. 복사할 map에 원소가 n개 있었다면, 복사하는 데 복잡도는 O(nlogn)이 아니라, O(n)에 수행됩니다. 단순하게 순회하면서 포인터만 잘 연결하면 되기 때문입니다. 문제는 이미 재구축된 맵을 또 다시 어딘가에 복사한다는 것에 있습니다. 이 부분을 어떻게 처리하면 좋을까요? swap을 이용하면 간단합니다.

 

 

---

 이 부분을 보시면, ref = new_ref 대신에 swap을 호출하였어요. 이는 단지, container x와 y를 바꿔주게 됩니다. new_ref와 ref를 바꾼다는 이야기는 new_ref에 있는 메타 데이터들과 ref의 메타 데이터들을 바꾼다는 의미입니다. 포인터와 레퍼런스, 이터레이터 등이 이에 속할 겁니다. 복잡도는 어떻게 될까요? O(1)만에 될 수 있습니다. 문서에도 그리 나와 있고요.

 

 

 사실 상식적으로 생각해 보면 간단합니다. 트리는, root의 주소만 가지고 있으면 되는데요. p1이 가리키고 있는 루트와 p2가 가리키고 있는 루트가 있을 겁니다. 이를 각각 r1, r2라고 해 봅시다. 즉, p1은 r1을 가리키고, p2는 r2를 가리키는 상황입니다. 그런데, 이걸 어떻게 바꾸면 될까요? p1이 r2를 가리키고 p2가 r1을 가리키게만 바꾸면 됩니다.

 

 

 간단합니다. 일일히 순회하면서 트리맵에 추가하는 것 보다는 연산이 훨씬 가벼움을 알 수 있습니다.

 

 

---

 이 부분은 어떨까요? 마찬가지로 오래 걸릴 수 있음을 알 수 있어요. 한 노드에 여러 개의 자식들이 달려 있을 때. 물론, 이 문제의 경우, 제일 오래 걸리는 케이스는 일반적인 tree case에서 오래 걸렸습니다. 그러므로, 백준에 표시되는 수행 시간은 103번째 줄이 있고 없고가 별 영향을 끼치지는 못했습니다만. 루트에만 여러 노드가 연결된 케이스의 경우는 이야기가 조금 달랐습니다.

 

 

 이 때에는, 한 노드에 연결 되는 것이 많으므로, 105번째 줄이 수행되었다면, 복사되어서 생성되었을 겁니다. 그런데, 이것도 복사해서 생성할 필요가 전혀 없습니다. 단지, 기존에 있던 map에 대해서 iterator만 가지고 오면 됩니다. 이렇게 바꾼 결과, 한 노드에 꽤 많은 노드가 연결된 full graph 케이스나 루트 하나에만 연결된 케이스에 대해서 유의미한 차이가 날 정도의 성능 향상이 있었습니다.