백준 18870 - 좌표 압축

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

문제 해결을 위해 두 개의 벡터 컨테이너를 사용했다.

하나는 문제의 입력을 그대로 저장한 배열 v로 결과값 출력에 사용한다.

다른 하나는 원소를 크기 순으로 정렬할 배열 v_sorted이다.

 

먼저 배열 v에 문제의 입력값을 저장하고, 벡터 생성자를 이용해 v_sorted도 생성한다.

STL에서 지원하는 sort와 unique, erase를 이용해 v_sorted 배열을 중복 없이 오름차순으로 정렬한다.

v_sorted가 완성되면 v의 각 원소 v[i]에 대해 v[i]와 일치하는 v_sorted 원소의 인덱스를 출력한다.

 

위 과정을 구현하기 위해 3가지 방법을 시도했으며 결과는 다음과 같다.

 

1) v_sorted 배열을 { key = 원소값, value = 인덱스} 형식의 해시맵에 저장

→ <int, int> 템플릿의 map 컨테이너를 생성했으나, key 값이 음수일 경우 인덱스 범위 초과 오류 발생 (왜??)

 

2) v_sorted 내에서 이진탐색을 통해 일치하는 원소 인덱스 계산

→ 테스트 케이스는 통과. O(log N)으로 시간 내에 문제를 해결할 수 있다고 생각했으나 시간 초과

 

3) STL 알고리즘의 lower_bound 활용

→ 이진탐색과 비슷한 시간복잡도를 가짐에도 시간 초과 없이 문제 해결 성공

 

<배운 내용, 느낀 점>

C++ (STL) 의 우월함을 확인할 수 있었던 문제.

 

사실 다른 두 방법의 문제점과 해결방법은 제대로 이해하지 못했지만,

여기에 주목하기보다는 우선 알고리즘 이론과 관련된 문제로 넘어가기로 했다.

 

다만 유용하게 쓰이는 STL 문법은 제대로 익혀야 할 필요를 느꼈다.