1.문제
2.풀이
처음에는 map을 활용하여 문제를 풀었고, 풀이는 다음과 같다
- n개의 숫자를 받아 tmp배열과 map에 각각 따로 저장한다.
- map은 자동 정렬이 되므로 map의 처음과 끝을 돌며 앞에 몇개의 숫자가 있는지 index 변수로 세어주고 각 key값의 value쌍으로 넣어준다
- tmp에는 처음 들어왔던 순서대로 숫자가 들어 가 있으므로 이를 활용해 주어진 숫자의 좌표를 순서대로 출력해준다.
하지만 답을 도출하는것은 성공했으나 시간복잡도에 걸려 정답을 받지는 못했다.
알고보니 map은 O(nlogn)의 시간복잡도를 가지긴 하지만 상수가 매우 큰 레드블랙 트리라는 자료구조를 사용하기 때문에 삽입/삭제에서 시간이 많이 소요될 수 있다고 한다.
그래서 새로운 방법을 찾아보았다.
- 먼저 출력 순서를 알기위한 원본 벡터(v)와 정렬을 하기 위한 카피벡터(cv)를 선언하고 값을 넣어준다.
- cv를 sort를 사용해 정렬해준다.
- erase + unique 함수를 사용해 중복값을 없애준다.
- lower_bound 함수를 원본벡터를 참조해서 사용해 순서대로 답을 출력한다
(이때, 정렬이 된 배열이므로 결국 인덱스의 값이 나보다 앞에 있는 값들의 갯수와 같다)
https://donggoolosori.github.io/2020/09/26/boj-18870/
3.배운점
- map은 자동 정렬이 되며, unique key를 가지므로 알아서 중복을 걸러준다.
- 벡터를 복사 할 때
vector<> cv(v)의 형태로 복사를 할 수 있다. - unique함수는 중복된 값을 모두 뒤로 보낸뒤 뒤로간 값의 첫번째 주소를 반환한다.
3-1 반환받은 주소부터end()까지 erase로 지워주면 중복이 제거된 배열을 얻을 수 있다. - lower_bound 함수는 나보다 크거나 같은 첫번째 원소의 '주소'를 반환한다.
4-1. 주소를 iter형태로 받으므로 배열이나 벡터의 첫번째 주소를 뺴주면 인덱스를 얻을수있다.
