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

문제링크 🚩

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

18870번: 좌표 압축

 

​

📕 문제 접근 📕

 

1. 해당 문제는 쉽게 크기에 따른 랭킹?(순위)를 지정해주는 프로그램을 작성하는거다 

 

- hashmap을 생성하여 ranking을 지정해줄 맵을 생성한다.

- 실제 배열 -> 최종적으로 비교할 배열 , 정렬배열 -> 정렬해서 숫자의 크기를 나열할 배열을 만든다

- 정렬배열을 정렬하여 크기를 비교한다

 

- 중복되지 않게 맵에 정렬 배열을  ranking에 넣어주고

- 실제 배열 위치에 ranking을 비교해서 출력하는 로직이다 

 

 

💻 Code 💻

 

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));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        HashMap<Integer, Integer> ranking = new HashMap<>();

        int real[] = new int[N];
        int sorted[] = new int[N];

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

        Arrays.sort(sorted);
        // -10, -9 ,2 ,4 ,4

        int rank = 0;
        for (int v : sorted) {
            /*
             *  이 때 만약 앞선 원소가 이미 순위가 매겨졌다면
               불필요한 연산을 막음
                           *
             */
            if (!ranking.containsKey(v)) {
                ranking.put(v, rank);
                rank++;
            }

        }

        // map -> 0(-10), 1(-9), 2(2), 3(4)

        StringBuilder sb = new StringBuilder();
        for (int key : real) {
            int ranked = ranking.get(key);    // 원본 배열 원소(key)에 대한 value(순위)를 갖고온다.
            sb.append(ranked).append(' ');
        }

        System.out.println(sb);


    }
}

💻 Code Review💻

- Arrays.sort() 부분에서 N이  1,000,000일 때 최악의 경우 N ^2 이기 때문에 굉장히 비효율적이라고 생각하지만 이를 해결 할 수 있는 방법을 아직 못 찾았다.  (아신다면 댓글 부탁드립니다!)