[백준] 정렬 No18870 좌표압축

문제

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

18870번: 좌표 압축

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

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

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

 

풀이

 

처음에는 아래처럼 풀었었다. 옛날에 비컴공 친구가 교양인가 뭔가로 프로그래밍 과제하는데 모르겠다고 도와달라고 했던 문제랑 똑같아서 첨엔 그 때 풀어준 방법대로 풀었다.

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		
		int num[]=new int[n];
		
		for(int i=0;i<n;i++) {
			num[i]=sc.nextInt();
		}
		
		int[] answer=new int[n];
		Arrays.fill(answer, n);
		for(int i=0;i<n;i++) {
			int a=num[i];
			for(int j=0;j<n;j++) {
				if(a<=num[j])
					answer[i]--;
			}
		}
		
		for(int i=0;i<n;i++) {
			System.out.print(answer[i]+" ");
		}
	}

}

근데 시간 초과가 나서(ㅎㅎ) 반복문을 한번만 쓸 수 있도록 HashMap을 이용해서 키에는 원래 좌표를, value에는 새로운 좌표를 넣어주었다. 그런데도 또 계속 시간초과가 나서 입출력 방식을 바꾸어주었다.

백준은 오랜만에 푸는데 역시 백준은 입출력 시간을 많이 신경 써줘야해서 불편하다ㅜㅜ.... Scanner가 편한데... 이 방법에도 익숙해져야 겠다.

 

코드

package Sorting;

import java.util.*;
import java.io.*;
public class No18870_좌표압축 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		
		String[] input=br.readLine().split(" ");
		int[]nums=new int[N];
		for(int i=0;i<N;i++) {
			nums[i]=Integer.parseInt(input[i]);
		}
		
		//원래 위치,새로운 좌표 
		HashMap<Integer, Integer>map=new HashMap<>();
		
		int[] nums2=new int[N];
		nums2=nums.clone();
		Arrays.sort(nums2);
		
		int idx=0;
		for(int i=0;i<N;i++) {
			if(!map.containsKey(nums2[i]))
				map.put(nums2[i], idx++);
		}
		
		StringBuilder sb=new StringBuilder();
		for(int n:nums) {
			sb.append(map.get(n)).append(' ');
		}
		
		System.out.println(sb.toString());
	}
	
}