https://www.acmicpc.net/problem/18870
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
접근 과정 / 풀이 과정
항상 그렇듯이 먼저 문제를 이해해야했다. 수직선에 좌표 N개가 있는데, 좌표 압축을 적용, 좌표 압축이란 것을 적용한 결과 Xi > Xj를 만족... 하는...? 서로 다른 좌표 Xj의 개수와 같아야 한다..? 그리고 적용한 결과들을 출력해야한다고 한다. 잘 이해가 안가서 예제출력을 보고 다시 문제를 읽어보았다.
예제 출력 덕분에 가까스로 이해가 되었다.
어떤 문제인지 감이 오자 어떻게 풀어야 할지 생각하였다.
단순하게 X1에 대하여 모든 값들을 한번씩 비교하면 어떨까? 자신보다 작은 숫자가 발견 되면 count 숫자가 1씩 증가하는 것이다.
아, 좌표의 개수 범위가 1부터 1,000,000이다. 무조건 시간 제한(2초)에 걸릴 것이다.
그렇다면 좌표 X1보다 작은 숫자들이 몇 개인지 알 수는 없을까? 흠,, 이럴 때 카운트 정렬이 참 좋을 것 같지만 수의 범위가 10의 9제곱으로 범위가 너무 넓다. 메모리가 터져버릴 것이다. 그럼 카운트 정렬의 비슷한 원리인 해시를 써보는 것은 어떨까?
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N = Integer.parseInt(bf.readLine());
st = new StringTokenizer(bf.readLine() , " ");
int[] arr = new int[N];
for(int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
// 복사한 배열
int[] copy = Arrays.copyOfRange(arr, 0, arr.length);
// 복사한 배열을 정렬
Arrays.sort(copy);
Hashtable< Integer , Integer > hash = new Hashtable<>();
int count = 0;
for(int i = 0; i < copy.length-1; i++) {
// 정렬된 배열을 0번째 값부터 해시테이블에 put한다.
if( copy[i] != copy[i+1] ) {
hash.put(copy[i], count);
count++;
}
}
hash.put(copy[copy.length-1],count);
for(int i = 0; i < arr.length; i++)
bw.write(hash.get(arr[i]) + " ");
bw.flush();
}
} 위 코드는 값이 들어있는 배열을 복사본을 하나 더 만들어서 정렬을 시킨다. 그리고 정렬된 배열을 0번째부터 count를 세면 자연스럽게 자신 밑으로 몇 개의 수가 있는지 알 수 있다.
정렬된 배열의 i번째 값을 키로, count를 value로 설정한다.
그럼 해시테이블로 원본의 i번째 값의 밑에 몇 개의 수가 있는지 알 수 있을 것이다.
느낀점
요즘엔 라이브러리를 가져다 사용하는 것이 마음에 들지 않는다. 이것은 내가 해당 클래스들을 구현할 줄 모르기 때문일 것이다. 이렇게 구현할 줄 모르는 라이브러리를 가져다 사용하여 문제를 풀면, 온전히 내 힘으로 풀지 않은 것만 같다.
그래서 1차 목표는 내가 사용하고 있는 메소드들의 원리와 구현방법을 학습하는 것이다. 그 뒤로부터는 사용하는데 있어 전혀 거리낌이 없을 것 같다.
