IT주짓수

문제

수직선 위에 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
• -109 ≤ Xi ≤ 109

예제 입력 1 

5

2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

import java.util.*;
import java.io.*;
import java.math.*;
import java.security.Key;

public class Q18870 {

		public static void main(String[] args) throws IOException {
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        int cnt = Integer.parseInt(br.readLine());
	        StringTokenizer st = new StringTokenizer(br.readLine()," ");
	        int res[] = new int [cnt];
	        
	        HashMap<Integer,Integer> xymap = new HashMap<Integer,Integer>();
	        
	        //map의 key 값은 중복 저장이 안되니, 사용자가 입력한 값을 key로받아서
	        for(int i=0;i<cnt;i++)
	        {
	            res[i]=Integer.parseInt(st.nextToken());
	            xymap.put(res[i],i);
	        }
		    br.close();   
	        int size = xymap.size();
       
	        //map의 key set을 value list에 넣고
	        ArrayList<Integer> value = new ArrayList<>();	        
	        Iterator<Integer> iter = xymap.keySet().iterator();
	        
	        while(iter.hasNext())
	        {
	             value.add(iter.next());
	        }
	        //오름차순 정렬
	        Collections.sort(value);
	        /*27~34까지가 단순히 오름차순 정렬을 위한 코드인데 좀 불필요한거같기도하고..
            넘긴거같기도하다 근데 map의 keyset만 바로 arraylist로 변환해서 저장하는 법을 모르겠음*/
	        
	        //key에 따른 좌표 압축된 숫자를 맞추어 map에 넣어주기
	        for(int i=0;i<size;i++)
	        {           
	            xymap.put(value.get(i),i);
	        }
	        
	        StringBuilder sb = new StringBuilder();
	        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	        
	        //사용자가 입력했던 res배열값이 xmap에 key로 있다면, 해당 key의 value(좌표압축된 숫자) 뽑아서 sb에 저장
	        for(int i=0;i<cnt;i++)
	        {
	                if(xymap.containsKey(res[i]))
	                  {
	                    sb.append(xymap.get(res[i])+" ");        	
	                  }
	         }      
	        
	        bw.write(sb.toString());
	        bw.flush();
	        bw.close();
	    }
	}

<제출 결과>

시간초과의 늪에서 허우적거리다가, 어드바이스를 받고 불필요한 이중 for문을 단일 for문(코드 맨마지막 for문)으로 바꾸고 bw 및 sb를 사용하여 시간을 줄였다.

나는 애초에 사용자가 입력한 키값의 중복을 제거하기위해 바로 map으로 입력받고,

중복이 제거된 map의 keyset을 arraylist로 변환하기위해 iterator를 사용하게되었다.

그런데 이 단계에서 시간이 너무 오래걸렸다.......

그렇게해서 정리하자면 아래와 같은 순서로 코드가 작성되었는데

[입력값 map에 put (중복값 제거) -> keyset 분리 (iterator 사용) -> arraylist 변환 (오름차순) -> 매칭하여 다시 map에 put(좌표 압축)]

다 제출하고 나서 비교해보니, 차라리 arraylist로 입력받고 오름차순 바로 sort로한 다음에, map 넣는게 굉장히 깔끔한것 같았다.

요렇게

[입력값 arraylist (오름차순) -> map에 put (중복값 제거) -> 매칭하여 다시 map에 put(좌표 압축)]

아무튼 더 좋은 방법은 항상 많은 것 같다. 힘내야지