JAVA 백준 18870 좌표 압축 (정렬)

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

 

---

문제

1. 첫째 줄에 좌표 개수 N (1 <= N <= 1000000)가 주어진다.
2. 둘째 줄에 공백 한 칸으로 구분된 좌표 (-10^9 <= 좌표 X <= 10^9) N개가 입력된다.
3. 결과로 좌표 N개를 압축하여 출력한다.

---

 

 

초기 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] list = new int[N];
        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            list[i] = num;
            set.add(num);
        }

        ArrayList<Integer> sortList = new ArrayList<>(set);
        Collections.sort(sortList);

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            sb.append(sortList.indexOf(list[i])).append(" ");
        }

        System.out.println(sb);
    }
}

 

 

시간 초과가 발생한 코드.

HastSet에 수를 넣어 중복을 제거하고 정렬하여 기존의 배열과 비교해 결과를 얻어내는 방법의 코드.

 

더 빠르게 탐색하여 수를 저장할 방법이 필요하다.

 

탐색할 때 역시 빠른 건 hash니까 hash를 이용하여 계속 진행해보기로 한다.

hashSet과 ArrayList를 이용했을 때 시간초과가 발생했으므로 HashMap을 이용하여 값을 출력에 이용하면 더 빠를 것 같다.

 

정렬된 좌표 리스트를 이용해 hashMap에 기존 좌표값 - 압축된 좌표값 세트로 map에 저장하여 이용하도록 한다.

hashMap에 저장된 값으로 value를 꺼내는 것은 시간이 훨씬 빠르므로 시간 초과가 발생하지 않을 것 같다.

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] list = new int[N];
        int[] temp = new int[N];
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            list[i] = num;
            temp[i] = num;
        }

        Arrays.sort(temp);

        for (int i = 0; i < N; i++) {
            if(!map.containsKey(temp[i])){
                map.put(temp[i], map.size());
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            sb.append(map.get(list[i])).append(" ");
        }

        System.out.println(sb);
    }
}