[Java/Python] 백준 18870번 - 좌표 압축

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

18870번: 좌표 압축

 

혼자 힘으로 풀었는가? : O

알고리즘 분류
 - 정렬
 - 값 / 좌표 압축

문제

수직선 위에 N개의 좌표 \(X_{1}\), \(X_{1}\), ..., \(X_{n}\)이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

\(X_{i}\)를 좌표 압축한 결과 \(X`_{i}\)의 값은 \(X_{i}\) > \(X_{j}\)를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

\(X_{1}\), \(X_{2}\), ..., \(X_{n}\)에 좌표 압축을 적용한 결과 \(X'_{1}\), \(X'_{2}\), ..., \(X'_{n}\)를 출력해보자.

 

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 \(X_{1}\), \(X_{2}\), ..., \(X_{n}\)이 주어진다.

출력

첫째 줄에 \(X'_{1}\), \(X'_{2}\), ..., \(X'_{n}\)을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• \(10^9\) ≤ Xi ≤ \(10^9\)

 

---

각 수를 정렬한 다음 정렬 한 수를 Hash나 Dict에 담아서 값을 호출해주면 되는 간단한 문제이다.

 

(Python 코드)

 

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))
set_data = set(data)
sort_data = list(set_data)
sort_data.sort()

cnt_data = {}
for i in range(len(sort_data)):
  cnt_data[sort_data[i]] = i

for i in range(len(data)):
  print(cnt_data[data[i]], end=' ')

 

data값을 set_data로 바꾸어 중복 값을 제거하여 반복문이 돌아가는 횟수를 줄여준 후

 

set_data를 sort_data에 다시 넣어서 정렬을 해준다.

 

이후 정렬된 각 값을 호출하며 dict에 넣어준 후 

 

기존 data를 호출하며 매칭 되는 dict값을 출력하면 끝.

---

 

자바도 크게 다를 바 없다.

 

(Java 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException   {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		String s = br.readLine();
		String [] s_arr = s.split(" ");
		int [] data = new int[n];
		int [] sort_data = new int[n];

		for(int i=0; i<n; i++) {
			data[i] = sort_data[i] = Integer.parseInt(s_arr[i]);
		}

		//quickSort(sort_data, 0, n-1);
		Arrays.sort(sort_data);

		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		int idx = 0;
		for(int i=0; i<n; i++) {
			if(!map.containsKey(sort_data[i])) {
				map.put(sort_data[i], idx++);
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n;i++) {
			sb.append(map.get(data[i])).append(" ");
		}
		System.out.print(sb);
	}
}

위와 크게 다르지 않으며

 

배열 단계에서 중복을 제거하지 않았기 때문에

 

HashMap에 넣을 때 중복을 확인하며 idx값을 조절하여 넣어주는 것만 조심하면 된다.

 

 

하지만...

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException   {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		String s = br.readLine();
		String [] s_arr = s.split(" ");
		int [] data = new int[n];
		int [] sort_data = new int[n];

		for(int i=0; i<n; i++) {
			data[i] = sort_data[i] = Integer.parseInt(s_arr[i]);
		}

		quickSort(sort_data, 0, n-1);
		//Arrays.sort(sort_data);

		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		int idx = 0;
		for(int i=0; i<n; i++) {
			if(!map.containsKey(sort_data[i])) {
				map.put(sort_data[i], idx++);
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n;i++) {
			sb.append(map.get(data[i])).append(" ");
		}
		System.out.print(sb);
	}
	private static void quickSort(int[] sort_data, int start, int end) {
		// TODO Auto-generated method stub

		if(start >= end) {
			return;
		}

		int pivot = start;
		int left = start+1;
		int right = end;

		while (left <= right) {
			while (left <= end && sort_data[left] <= sort_data[pivot]) {
				left += 1;
			}
			while(right > start && sort_data[right] >= sort_data[pivot]) {
				right -= 1;
			}

			if(left > right) {
				int tmp = sort_data[pivot];
				sort_data[pivot] = sort_data[right];
				sort_data[right] = tmp;
			} else {
				int tmp = sort_data[pivot];
				sort_data[pivot] = sort_data[left];
				sort_data[left] = tmp;
			}
		}
		quickSort(sort_data, start, right-1);
		quickSort(sort_data, right+1, end);
	}
}

처음 내가 작성한 코드는

 

Arrays.sort()를 사용한 코드가 아닌

 

퀵 정렬을 사용한 코드를 작성하려 하였으나..

 

내가 할 땐 잘 되는데 제출하면 '틀렸습니다.'를 봐버려서

 

어디가 문제인지 반례도 못 찾아버렸다...

 

 

퀵 정렬에대해서 좀더 공부해야겠다.

 

사실 퀵정렬 구현할 때 어떻게 구현하는지 까먹어서 내 게시글 보면서 구현했다.

 

난 아무래도 정렬 알고리즘이 너무 약하다...