(Java) 백준 18870 - 좌표 압축

N의 입력 크기가 1,000,000 까지 가능하므로 2중 for문을 사용해서

단순 비교를 하면 바로 시간초과가 날것을 예상했다. 그래도 한번 작성해 보았는데

1%에서 바로 시간초과가 난다.

어떻게 해야 할지 30분 정도 고민을 하다가 검색을 통해 힌트를 얻었다.

 

문제 해결의 키포인트는 정렬이다.

각 입력값을 낮은값부터 순위를 매겨서 처리하는것이다.

각 입력값에 대한 순위값을 출력하면 된다.

HashMap을 이용해서 입력값과 순위값을 넣고 원본 배열과 비교하며 출력하면 된다.

구현이 어려운 문제는 아니지만 정렬이 필요하다는것과 적절하게 HashMap을 사용해야 한다는

생각을 하기 쉽지 않았다.

---

실패 코드(시간 초과)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < n; i++) {
            int cnt = 0;
            int temp = arr[i];
            HashSet<Integer> hs = new HashSet<>();
            for (int j = 0; j < n; j++) {
                if (temp > arr[j]) {
                    if (hs.contains(arr[j])) {
                        continue;
                    } else {
                        hs.add(arr[j]);
                        cnt++;
                    }
                }
            }
            sb.append(cnt).append(" ");
        }

        System.out.println(sb);
    }
}

 

최종 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] sortArr = arr.clone();
        Arrays.sort(sortArr);

        HashMap<Integer, Integer> hm = new HashMap();
        int rank = 0;
        for (int i = 0; i < n; i++) {
            if (!hm.containsKey(sortArr[i])) {
                hm.put(sortArr[i], rank++);
            }
        }

        for (int i = 0; i < n; i++) {
            sb.append(hm.get(arr[i])).append(" ");
        }

        System.out.println(sb);
    }
}