Baekjoon18870: 좌표 압축

좌표 압축

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

18115

7986

6011

42.610%

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -10^9 ≤ Xi ≤ 10^9

 

풀이

정렬을 수행하는 결과값이 아닌 원래 위치에 정렬 순서를 입력해야한다. 입력 최대값이 10의 9승으로 매우 크기 때문에 카운팅 정렬을 사용하지 않고 다른 방법을 생각해보았다.

2차원 배열을 사용한다. 입력된 숫자와 index를 저장하고 숫자의 크기에 따라 정렬을 수행한다. 

예제 1을 2차원 배열로 나타내면 다음과 같다

2	4	-10	4	-9
0	1	2	3	4

이것은 숫자 기준으로 정렬하면

-10	-9	2	4	4
2	4	0	1	3

[N]크기의 배열을 만들고 순서를 넣어준다. 반복문을 통해 0부터 숫자를 집어넣는다

[2] index → 0

[4] index → 1

[0] index → 2

[1] index → 3

[3] index → 3

순서대로 출력하면 2 3 0 3 1 이 나온다

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int[][] arr = new int[N][2]; // [0]에 숫자를 넣어주고 [1]에 원래 index를 기록
		int[] sorted = new int[N]; //정렬 후 저장된 index에 순서를 넣어준다
	
    	StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i][0]=Integer.parseInt(st.nextToken());
			arr[i][1]=i;
		}
        //2차원 배열 오름차순 정렬
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
					if(o1[0]==o2[0]) return o1[1]-o2[1];
					else return o1[0]-o2[0];
			}});
            
	   int start=0; //순번을 기록할 변수 
	   sorted[arr[0][1]]=0; //처음항은 값을 넣어준다
       
       for(int i=1; i<N;i++) {
			if(arr[i][0]!=arr[i-1][0])start++; //이전값과 같다면 동일한 순위므로 값을 증가X
			sorted[arr[i][1]]=start; //순서를 index에 맞게 넣어준다
		}
       for(int i=0; i<N;i++) {
			bw.write(sorted[i]+" ");
		}
       bw.flush();
       bw.close();
 }}