문제 출처
https://www.acmicpc.net/problem/18870
오답 원인1
배열에서 중복되는 값을 제거하는 방법이 생각나지 않았다.
오답 원인2
시간복잡도 $O(n^2)$ 으로 풀었으나 시간초과로 틀렸다.
오답 풀이
중복되는 값은 <algorithm> 헤더에 있는 unique 함수를 사용하면된다.
선형 탐색을 하는 내부 반복문을 이진 탐색으로 바꾸었다.
시간복잡도가 $O(n^2)$ 에서 $O(nlogn)$ 으로 개선되면서 통과하였다.
전체 풀이
- 주어진 배열을 복사한다.
- 복사된 배열을 정렬하고 중복값을 제거한다.
- 주어진 배열을 복사된 배열에 비교하여 인덱스를 찾는다.
- 찾은 인덱스를 새로운 배열에 저장한다.