[백준 18870] 좌표 압축 자바(Java) 풀이

문제 링크 : 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 ] 

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​

 

[ 풀이 ] 

조금 생각해봐야 할 문제였던 거 같아요.

우선 HashMap과 원래 배열 arr, 정렬된 배열 sorted 배열을 만듭니다.

arr

2

4

-10

4

-9

sorted

-10

-9

2

4

4

만약 map에 없다면 key값을 넣고 value값을 1씩 증가시켜주면 랭킹처럼 value가 저장되게 됩니다.

map	-10	-9	2	4	key
	0	1	2	3	value

거의 다 왔습니다!

이제 arr을 반복문에 돌려 순서대로 map에 있는 value(즉, 등수)를 가져옵니다.

ex) arr[0] 의 value값은 2, arr[1] 의 value값은 3

따라서 2 3 0 3 1 이란 출력이 나오게 됩니다.

 

 

[ 결과 ]

 

 

[ 정답 코드 ] 

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

public class Main {
   static int N;
   static int[] arr;
   static int[] sorted;

   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      Map<Integer, Integer> map = new HashMap<>();

      N = Integer.parseInt(br.readLine());
      arr = new int[N];
      sorted = new int[N];
      int count = 0;
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int i = 0; i < N; i++) {
         arr[i] = sorted[i] = Integer.parseInt(st.nextToken());
      }

      Arrays.sort(sorted);

      for (int v : sorted) {
         if (!map.containsKey(v)) {
            map.put(v, count);
            count++;
         }
      }

      StringBuilder sb = new StringBuilder();
      for (int key : arr) {
         int ranking = map.get(key);
         sb.append(ranking).append(" ");
      }
      System.out.println(sb);

   }
}