[Java] 백준 18870번 : 좌표 압축

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를 출력해보자.

[입력]

첫째 줄에 N이 주어진다.

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

[출력]

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

 

[제한]

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

[예제 입력]

[풀이과정]

제한 조건을 보면 수가 굉장히 크다. 따라서 쓸데없는 for문을 많이 쓰면 시간초과가 난다. 

 

X[i] 보다 작은 수가 몇개인지 구하는 문제이다.  

 

1) 입력 값들을 크기가 작은 순으로  정렬한다.

-> 이렇게 정렬하면 x[i] 보다 작은 수는 x[i]의 왼쪽 편에 있게 된다. 

-> 한칸씩 넘어갈때마다 +1씩 세어주면 자기보다 작은 값의  수를 셀 수 있다.

2)   HashMap을 이용하여 ( X[i] , rank) 로 저장한다.

-> 같은 수는 한번만 취급하기 때문에 이미 저장되어있는 Key = X[i] 가 있다면 저장하지 않는다.

 

3) 원본의 배열 값을 가지고 hashmap.get()을 통해 value값을 차례로 찾아주면 된다.

[코드]

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

//좌표 압축 1.해쉬
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //좌표 개수
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();
        HashMap <Integer, Integer> hashMap = new HashMap<>();
        int rank = 0;

        int [] x = new int[N];//원래 배열
        int [] x_sorted = new int[N]; //정렬된 배열



        for(int i = 0 ; i <N ; i++){
            x[i] = x_sorted[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(x_sorted); // x좌표들을 정렬해준다.
        //정렬한대로 첫번째 수부터 rank = 0이다.


        for (int i = 0 ; i <N ; i++){
            if(!hashMap.containsKey(x_sorted[i])) { //x 좌표가 중복일경우는  put 하지 않는다.
                hashMap.put(x_sorted[i], rank);
                rank++;
            }
        }


        for(int key : x) {
            int r = hashMap.get(key);	//x 배열의 key값으로 순위값을 (rank)를 가져오면된다.
            sb.append(r).append(' ');
        }

     System.out.print(sb);



    }
}

 

[결과]