c++ unique 함수 : 정렬을 먼저 해야 중복이 제거된다.

 좌표 압축이라는 기술이 있다고 들었습니다. 물론, 저는 ps를 하지 않아서 잘 모르겠습니다. 좌표 압축을 위해서, 중복을 제거해야 하는데요. 그 때 많이 쓰는 함수가 sort + unique + erase 조합입니다. 아마도 그러리라 생각이 듭니다. 물론 set, map도 됩니다만. 이것은 제 전문이 아니니 논외로 하겠습니다. 이 중, unique가 어떻게 동작하는지 이해해 보도록 하겠습니다.

 

 

---

 cpp reference 코드에 나온 코드는 아래와 같습니다.

 

 

  아. 보기만 해도 힘드네요. 일단, result, first, last 세 개가 있습니다. 이 셋을 기준으로 보도록 하겠습니다. 보통 unique를 쓰실 때, unique(v.begin(),v.end()) 이런 식으로 쓰실 거니, last는 자료구조의 끝을 가리키고 있을 겁니다.

 

 

 이런 상황입니다. first가 한 칸 뒤로 이동했을 때, last와 같은 곳을 가리키지 않습니다. 따라서, 안쪽 Loop를 돕니다. 

 

 

 여기서, result가 가리키는 값과 first가 가리키는 값이 다르므로, result도 한 칸 증가합니다.

 

 

 그리고, first가 가리키는 공간에 있는 값을 result에 넣어버립니다. 이제 다음 while Loop를 돌 건데요. first는 역시 1칸 증가합니다.

 

 

 first가 가리키는 값과 result가 가리키는 값을 비교할 건데요. 같네요. 8번째 if문에 걸리지 않으므로, 아무 일도 일어나지 않습니다.

 

 

 다음에 보면, first가 가리키는 값과 result가 가리키는 value가 각각 3과 2로 다릅니다.

 

 

 그러면 if문에 걸리기 때문에, result가 하나 증가합니다. 그리고 (*result) = (*first)에 의해서, 2번째 위치에 3이 들어갑니다.

 

 

 그 다음에, first를 1칸 증가시키면, last에 도달합니다. 이 상황에서 result를 한 칸 이동시키고 return을 시킬 거에요. 11번째 줄이 그것을 의미합니다. 정렬이 되어 있다는 전제가 깔렸다면, result 이후부터는 이미 자료구조에 있는 원소가 중복해서 등장할 거니 볼 필요도 없을 겁니다.

 

 

---

 그러면 sort가 되어 있지 않다면 어떻게 될까요? a b a 꼴 데이터를 만들어서 간단하게 어떻게 실행이 되는지 보도록 하겠습니다.

 

 

 처음 while loop 안에서, res와 first, last는 다음과 같이 되어 있을 거에요. 여기서 result와 first가 가리키는 값이 다릅니다. 따라서 8번째 if문에 걸리게 되고, r도 같이 증가합니다.

 

 

 그러면 이렇게 될 거에요. 이 때, 2번째 while loop의 조건에 걸릴 때, first++가 실행됩니다.

 

 

 이 때, 두 요소가 가리키는 값이 같나요? 다릅니다. 2와 1은 같은 수가 아닙니다.

 

 

 고로 두 개의 포인터 역시 ++이 될 겁니다.

 

 

 이 시점에서 이미 끝난 겁니다. sort가 안 된 데이터 구조에서 c++의 unique 함수는 의도대로 동작하지 않는다는 것을 알 수 있어요. 따라서, unique를 하기 전에 sort를 먼저 해야 합니다.