[코딩테스트/백준 알고리즘] 18870번 - 좌표 압축 (Java, 자바 풀이)

문제

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

18870번: 좌표 압축

---

문제 설명

---

문제 풀이

 

---

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        Map<Integer, Integer> map = new HashMap<>();
        int N = Integer.parseInt(br.readLine());
        int[] input = new int[N];
        int[] zip = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            input[i] = zip[i] = num;
        }
        Arrays.sort(zip);

        int value = 0;
        for (int key : zip) {
            if (!map.containsKey(key)) {
                map.put(key, value++);
            }
        }

        for (int i : input) {
            bw.write(map.get(i) + " ");
        }
        bw.close();
    }
}

 

<시간 초과>

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        Map<Integer, Integer> map = new HashMap<>();
        int N = Integer.parseInt(br.readLine());
        List<Integer> input = new ArrayList<>();
        List<Integer> zip = new ArrayList<>();
        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            input.add(num);
            if (!zip.contains(num)) {
                zip.add(num);
            }
        }
        Collections.sort(zip);

        for (int i = 0; i < zip.size(); i++) {
            if (!map.containsKey(zip.get(i))) {
                map.put(zip.get(i), i);
            }
        }

        for (int i : input) {
            bw.write(map.get(i) + " ");
        }
        bw.close();
    }
}