Tutorial : unique timer 1s memory 1024MB

배열의 중복 원소를 지우고 싶은 경우 어떻게 하면 좋을까?

std::unique를 이용하면 이를 쉽게 처리할 수 있다.

엄밀히 말하면 std::unique는 중복 원소를 지워주는 함수가 아니고, 연속으로 붙어 있는 중복 원소들 중 하나씩 남기고 나머지는 뒤로 보내주는 함수다. 또한 새로운 끝 위치(iterator)를 반환할 뿐, 크기를 줄이지도 않는다.

1. std::unique란?

ForwardIt unique( ForwardIt first, ForwardIt last );

• #include <algorithm> 헤더가 필요하다.

• [first, last) 구간에서 연속으로 같은 값이 반복되는 원소를 한 개만 남긴다.

• 나머지 원소들은 뒤로 보낸다.

• 그 결과로 “유효한 원소들이 끝나는 위치”(new end)를 반환한다.

2. 사용법

unique는 연속으로 같은 값이 붙어있는 경우에만 사용이 가능하기에 우선적으로 정렬이 필수다.

int arr[10] = {5, 2, 5, 3, 2, 2, 5, 3, 5, 1};

sort(arr, arr+10);
int N = unique(arr, arr+10) - arr;

printf("%d\n", N);
for(int i=0;i<N;++i){
    printf("%d ", arr[i]);
}

<출력>

4

1 2 3 5

1. 초기 상태: \{5, 2, 5, 3, 2, 2, 5, 3, 5, 1\}

2. 정렬 후에: \{1, 2, 2, 2, 3, 3, 5, 5, 5, 5\}

3. 최종 상태: \{1, 2, 3, 5, 2, 2, 3, 5, 5, 5\}

3. 벡터(vector)에 사용하는 경우

배열의 크기는 고정이라 N을 사용하여 관리하면 되지만, std::vector는 일반적으로 아래와 같이 사용한다.

vector<int> v = {5,2,5,3,2,2,5,3,5,1};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

• 벡터.erase(s,e)는 이터레이터 s부터 이터레이터 e 전까지의 원소를 제거한다.

[문제]

길이 N의 수열 A_1, A_2, \cdots, A_N이 주어졌을 때, 아래 두 정수 X와 Y를 구하여 출력하는 프로그램을 작성하시오.

1. 연속 중복만 제거했을 때 남는 길이 X.

   • \{1, 1, 2, 1, 1, 3, 3, 2\} -> \{1,2,1,3,2\}

   • X = 5

2. 전체 중복 제거(서로 다른 값만) 했을 때 남는 길이 Y.

   • \{1, 1, 2, 1, 1, 3, 3, 2\} -> \{1,2,3\}

   • Y = 3