[백준 18870] 좌표 압축 (S2)

📍 문제 

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

 

📍 문제 풀이

 

결국은 나보다 작은 숫자는 몇개인지를 카운팅하는 문제였다.

그러기 위해서는 정렬이 필요한 문제

여기서는 오름차순 정렬이 필요하다

 

입력받을 배열을 하나 만들고, 정렬된 값을 저장할 배열을 하나 만든다

하나만 만들어서 정렬을 하게되면 처음에 입력받은 숫자들의 값을 기억하지 못하기 때문에 두 개의 배열이 필요하다

정렬된 배열에서 하나씩 검색하며 인덱스값을 출력해도 되겠지만, 

그렇게 되면 시간초과가 뻔하기 때문에 `HashMap`을 사용

key값으로 정렬된 값, 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;

public class boj_18870 {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int n = Integer.parseInt(br.readLine());

       int[] nums = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          int cur = Integer.parseInt(st.nextToken());
          nums[i] = cur;
       }

       int[] sorted_nums = nums.clone();
       Arrays.sort(sorted_nums);

       HashMap<Integer, Integer> maps = new HashMap<>();
       int idx = 0;
       for (int num : sorted_nums) {
          if(!maps.containsKey(num)) {
             maps.put(num, idx++);
          }

       }

       StringBuilder sb = new StringBuilder();
       for (int num : nums) {
          sb.append(maps.get(num)).append(" ");
       }
       System.out.println(sb);
    }
}