[JAVA] 백준 18870. 좌표 압축

이 글은 읽는데 약 7분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

출력

첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.

제한

  • 1 ≤ N ≤ 1,000,000
  • -109 ≤ Xi ≤ 109

요약

숫자 리스트가 주어지고, 이 리스트의 숫자의 순서대로 리스트 전체에서 각 숫자보다 작은 숫자의 개수를 출력한다. 다만 작은 숫자 중 같은 숫자가 있어도 카운팅은 한 번만 한다.

풀이 과정

돌아가는 과정은 쉽게 생각했다. 그러나 문제는 시간초과!
생각한대로 코드를 짜서 제출하면 답은 맞으나 시간초과로 틀려버렸다…

일단 내가 생각한 방법은 입력받은 좌표 리스트를 두 개 만든다.

한개는 원본 그대로 두어서 마지막 출력할 때 순서대로 출력하기 위해 쓰며, 다른 하나는 오름차순 정렬을 한다.

이 때 좌표 리스트를 만들면서 하든 나중에 확인할 때 하든 정렬할 때 쓸 리스트에 중복 값이 들어가지 않도록 한다.

정렬이 되었다면 해당 숫자의 인덱스가 곧 그 숫자보다 작은 수의 개수이므로, 원본 좌표 리스트에서 숫자를 차례대로 꺼내면서 해당 숫자의 정렬된 리스트 상의 인덱스를 출력한다.

마지막을 위해서 아마 indexOf등을 쓰는데 이게 시간 초과의 원인이 아닐까 싶다. 이놈은 배열을 처음부터 값을 찾을 때까지 순회를 하는것이 시간이 너무 오래 걸리는 것 같다.

이를 해결하기 위해 HashMap을 쓴다. 해시맵은 리스트와 다르게 키를 주면 값을 찾는데 상수 시간이 걸린다. 즉, 어떤 값을 찾던 간에 찾는데 걸리는 시간을 똑같고 빠르다.

실패했던 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        String[] inputs = br.readLine().split(" ");
        ArrayList<Integer> arr = new ArrayList<>();
        
        for(String s : inputs){
            int n = Integer.parseInt(s);
            
            if(arr.indexOf(n) == -1) arr.add(n);
        }
        
        Collections.sort(arr);
        
        for(int i=0; i<N; i++){
            int n = Integer.parseInt(inputs[i]);
            sb.append(arr.indexOf(n));
            sb.append(" ");
        }
        
        System.out.println(sb.toString());
        br.close();
    }
    
}

정렬된 리스트에서 indexOf로 숫자를 찾고 있다. 이러면 시간 초과이다.

정답 코드

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

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        String[] inputs = br.readLine().split(" ");
        int[] origin = new int[N];
        int[] sorted = new int[N];
        
        for(int i=0; i<N; i++){
            int n = Integer.parseInt(inputs[i]);
            
            origin[i] = n;
            sorted[i] = n;
        }
        
        Arrays.sort(sorted);
        
        HashMap<Integer, Integer> hm = new HashMap<>();
        int j = 0;
        for(int i=0; i<N; i++){
            if(!hm.containsKey(sorted[i])){
                hm.put(sorted[i], j);
                j++;
            }
        }
        
        for(int i=0; i<N; i++){
            sb.append(hm.get(origin[i]));
            sb.append(" ");
        }
        
        System.out.println(sb.toString());
        br.close();
    }
    
}

정렬된 리스트로부터 해시맵을 만든다.

키는 해당 인덱스의 값을, 값에는 해당 값의 인덱스를 넣는다. 이 때 이미 존재하는 값은 카운팅을 하지 않으므로, 인덱스 세는 변수를 따로 만들어두고 해시맵에 추가하지 않은 값일 때만 인덱스를 올리며 추가한다.

이후 마지막에서 출력을 할 때는 해시맵으로 부터 값의 인덱스(=값보다 작은 수의 개수)를 가져와서 출력한다.

댓글