[필수개념] 중복된 요소를 제거하는 방법과 unique()

[필수개념] 중복된 요소를 제거하는 방법과 unique()

오늘은 중복된 요소를 제거하는 로직을 살펴보도록 하겠습니다. 정말 코딩 테스트에서 많이 나오는 로직이에요.

이거를 푸는 방법이 두 가지가 있는데, 두 가지에 대해서 좀 얘기를 해보도록 할게요.

---

첫 번째는 예를 들어서 배열이 이렇게 있다고 할게요.

그런데 여기 중에서 중복된 거를 다 제거해서, 오름차순으로 뽑아내는 로직이 있다고 합시다.

그럼 이렇게 뽑아내는 거겠죠.

첫 번째 방법은 Map을 사용하는 거예요. 사실은 배열을 사용해도 돼요.

Map을 사용해가지고 1이라는 Key에 배열의 원소인 1이 들어오면, 일단 Key 값(value)에 1을 할당해요.

그리고 나서 배열을 순차적으로 탐색하면서 배열의 원소가 또 1이죠. 그럼 key 값을 확인해봅니다.

그래서 1이라는 Key의 어떤 Value가 있어요. 그럼 continue. 그 다음에 원소 2가 들어오고, 2라는 Key에 아직 value가 없으니까 값을 할당하겠죠. 그리고 그 다음 원소인 2를 보고, 2라는 Key에 값이 이미 있으니까 넘어갈 겁니다. 그 다음에 3이 오네? 그럼 3에다가 값 할당, 이런 식으로 하는 방법이 있습니다.

자 이거를 코드로 쉽게 구현을 해보도록 할게요.

일단 vector를 {1, 1, 2, 2, 3, 3}으로 선언했습니다. 여기서 중복된 요소를 끄집어 낼 거예요.

그 다음에 map을 사용하기 위해서 mp를 만드는데, key도 int고 value도 int니까 map<int, int>로 선언합니다.

그 다음에 순회를 합니다.

순회를 하면서, 만약에 mp[i]에 값이 있다면, 즉 i 라는 Key 값에 할당된 Value가 있다면, continue; 를 하고, 없다면 mp[i]에 1을 할당해줍니다.

그리고 그 다음에 Map을 순회하면서,

새로운 배열인 ret에다가 값을 집어넣을 거예요. first는 Key고, second는 Value죠.

이렇게 해서 출력을 합니다. 컴파일을 해서 실행을 해보면,

잘 나옵니다.

우리가 원하던 바로, 중복된 배열에서 중복을 제거한 것을 뽑아낸 걸 볼 수가 있습니다.

로직은 map을 순회하면서, 배열의 요소에 해당하는 Key값에 value가 존재하면 continue하고, 그게 아니면 value를 할당해주는 거예요.

이게 첫 번째 방법입니다.

물론, 이러한 Map 대신에 count 배열을 만들어서 할 수도 있어요.

이런 식으로 Map과 비슷한 역할을 할 수 있습니다.

---

두 번째 방법은 unique() 함수를 사용하는 거예요.

unique는 범위안의 있는 요소 중 앞에서부터 서로를 비교해가며 중복되는 요소를 제거하고 나머지 요소들은 삭제하지 않고 그대로 두는 함수입니다. 그리고 O(n)의 시간복잡도를 가집니다.

만약에 1, 1, 2, 2, 3, 3이 있다고 쳐요.

그리고 앞에서부터 서로 서로 비교합니다. 똑같죠? 똑같으면 싸워가지고 한 명을 죽여버립니다.

" 너 나랑 똑같냐? 그럼 안 돼 이자식아 " 하면서 죽여요.

그럼 다른 1이 흐어엉 하면서 사라져요. 그리고 1은 앞에 남게 되죠.

그 다음에 1과 2를 비교하고, 똑같지 않으면 그냥 내버려둡니다. 2랑 2랑 비교하면 똑같으니까 또 싸우겠죠.

그럼 배열의 원소가 원래는 6개였는데, 그럼 나머지 것들은 어떻게 하냐?

그대로 옵니다. 그러니까 원래의 배열에서 중복을 제거한 다음, 중복을 제거한 배열의 원소를 앞에서부터 채우고, 남은 자리가 있으면 남은 자리는 원래 배열에 그 위치에 있던 나머지 애들이 오는 게 바로 unique() 함수입니다.

그럼 교안에 있는 예제 코드로 실습을 해볼게요.

여기를 보면, 중복을 제거한 뒤의 배열인 1 2 3 4 5가 앞으로 오고, 나머지 5자리를 그 위치에 있던 애들이 그대로 채웁니다.

그리고 unique()는 이터레이터를 반환하는데, 중복이 제거된 배열을 앞에서부터 채운 인덱스(4번째)의 다음의 5번째 이터레이터를 반환합니다.

즉, unique()는 중복되지 않은 배열을 채우고 난 다음의 위치를 반환하는 거죠.

그래서 5를 반환하는 겁니다. 4번째(인덱스)까지는 중복을 제거한 배열이고, 5번째 이터레이터를 반환한다고 보면 됩니다.

하나의 예시를 더 들어보겠습니다.

그러니까 앞에서부터 중복되지 않은 수를 이렇게 만들어 놓고 나머지는 그대로 채워놓는 거죠.

그래서 이렇게 나옵니다. 그러면 이건 어떻게 활용이 될까요?

이건 sort와 함께 써야합니다. 만약에 v를 바꿔서

이렇게 돌린다고 하면, 출력이

이렇게 나옵니다. 중복이 완전히 제거되지 않았죠.

unique()는 정말 단순하게, 앞에서부터 중복되는 거를 찾아가지고 하나로 없애는 거예요. 얘한테는 이 원소가 앞에 또 나왔던 것인지, 뒤에 또 나올 것인지는 중요하지 않습니다.

만약에 {2, 2, 1, 1, 1, 2, 2, 3, 3, 5, 6, 7, 8, 9}라면, 1에서 2개씩 연쇄적으로 하나를 없애면서 2, 1, 2, 3, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9 이렇게 남겠죠.

그냥 치고나가면서 앞에서부터 서로서로 두개씩 비교하는 거예요.

내가 원하는 건 이런 게 아니죠. 내가 원했던 것은 1, 2, 3, 5, 6, 7, 8, 9 이렇게 나오길 바랐는데, 앞에 2가 나와버리죠.

앞에서부터 차근차근 비교하는 게 unique() 이기 때문에, unique() 라는 함수로 중복되지 않은 배열을 뽑아내려면, sort를 하셔야 돼요.

sort를 써서 아래처럼 만들어야된다는 거죠. 그래야 앞에서부터 순차적으로 중복된 거를 비교해서 죽여버리는 로직을 해도 원하는 대로 나오겠죠.

그래서 어떻게 해야하냐면,

이렇게 하시면 됩니다. sort로 오름차순 정렬을 한 뒤,

unique 함수가 중복을 제거한 다음의 이터레이터를 반환하니까 거기서부터 원래의 배열 끝까지를 제거하는 거죠.

이렇게 하고 다시 실행해보면, 우리가 원했던 값들이 나오는 걸 볼 수 있습니다.

'근데 선생님, erase는 뭐죠?'

먼저, unique()는 3번째 인덱스의 이터레이터를 반환하죠. 그럼 우리가 출력하고자 하는, 중복되지 않은 배열은

여기까지니까 3번째 인덱스, 여기서부터

끝에까지 지워야됩니다.

그래서 erase(from, to)인데 [from, to) 범위로 지웁니다.

그리고 end가 저 동그라미 친 곳을 반환하기 때문에,

erase를 이런 식으로 써줘야됩니다.

이렇게 해서 중복된 요소를 제거하는 로직에 대해서 살펴봤습니다.