[백준] 좌표압축(18870) - Java

문제

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

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

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

---

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

첫째 줄에 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

예제 입력 2

 

6
1000 999 1000 999 1000 999

 

예제 출력 2

1 0 1 0 1 0

 

 

 

 

내가 푼 코드

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

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());
        int[] origin = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            origin[i] = Integer.parseInt(st.nextToken());
        }
		
        // 정렬한 배열
        int[] sorted = Arrays.copyOf(origin, N);
        Arrays.sort(sorted);
        
        // map에 담아줌(중복제거를 위하여)
        int rank = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i=0; i<N; i++) {
            if ( !map.containsKey(sorted[i])) {
                map.put(sorted[i], rank);
                rank++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<N; i++) {
            sb.append(map.get(origin[i]) + " ");
        }
        System.out.println(sb.toString());
    }
}

 

문제 이해

일단 문제는 주어진 배열을 좌표 압축 하는 문제인데 좌표 압축이란? 해당 배열의 값이 몇인지는 중요하지 않고 그 값이 몇번째로 작은값인지 값에 순위를 메겨서 출력해주는 것이다.

 

예제 입력 1의 예제인 [2, 4, -10, 4, -9] 의 경우 2는 3번째로 작은수이지만 시작 값이 0 부터 이므로 3-1 = 2

4는 4번째로 작은수이므로 4-1 = 3

-10은 1번째로 작은수이므로 1-1 = 0

...

 

 

이런식으로 표시해준다.

 

그럼 출력값은 [2, 3, 0, 3, 1] 이 된다.

 

 

푸는 방법

1. 원본 배열을 복사한 배열을 만들어 준 다음 정렬해준다. (오름차순 정렬)

2. 중복값의 경우 같은 순위를 가져야하기 때문에 set, map 과 같은 자료구조를 써야하는데 map을 사용한다.

   - key : 정렬된 배열의 숫자 순서대로 

   - value : 순위

3. map의 key에 숫자를 넣어주므로 key는 중복되지 않고, containsKey() 메서드를 이용하여 key 중복여부를 확인 후 map에 값을 넣어준 다음 rank를 +1 해준다.

4. 마지막에 for문을 이용하여 System.out.println()으로 출력하면 시간초과 발생하여 StringBuilder 사용한다.