18870번 : 좌표 압축

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

18870번: 좌표 압축

 

 

문제

 

 

코드

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

public 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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        //O(n)
        ArrayList<Integer> input = new ArrayList(n);
        for(int i=0;i<n;i++) {
            input.add(Integer.parseInt(st.nextToken()));
        }

        HashSet<Integer> inputSet = new HashSet<>(input); //중복값 제거
        Integer[] newArr = inputSet.toArray(new Integer[0]);
        Arrays.sort(newArr);

        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<inputSet.size();i++) {
            map.put(newArr[i],i);
        }

        //O(n)
        for(int i=0;i<n;i++) {
            sb.append(map.get(input.get(i)) + " ");
        }
        bw.write(sb+""); bw.flush();

    }
}

 

 

해결방법

많은 시도 끝에 푼 문제이다. 처음에 그냥 ArrayList 2개를 사용해 하나는 값을 입력받고, 하나는 중복된 값빼고 오름차순 정렬하여 값을 입력받은 ArrayList와 비교하여 출력하는 식으로 풀었다. 나름 속도를 높인다고 BufferedReader, BufferedWriter, StringBuilder, StringToken을 사용했지만 "시간 초과"가 떴다.

 

 

ArrayList 2개 사용한 코드 (시간 초과)

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

public 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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        ArrayList<Integer> input = new ArrayList(n);
        ArrayList<Integer> inputSort = new ArrayList(n);
        //O(n^2)
        for(int i=0;i<n;i++) {
            int num = Integer.parseInt(st.nextToken());
            input.add(num);
            if(!inputSort.contains(num))
                inputSort.add(num);
        }
        Collections.sort(inputSort);
        
        //O(n^2)
        for(int i=0;i<n;i++) {
            sb.append(inputSort.indexOf(input.get(i)) + " ");
        }
        bw.write(sb+""); bw.flush();
    }
}

 

머리 속을 스쳐간 생각으로 HashSet이나 HashMap을 사용해도 속도는 비슷할 것이라고 생각했다. 하지만 HashSet과 HashMap을 사용하면 속도는 훨씬 빨라진다. 이를 몰랐던 이유는 자바 컬렉션들의 시간 복잡도에 대해 무지했기 때문이다. 자바 컬렉션(HashMap, List, ...)들의 시간복잡도가 궁금하다면 여기를 클릭하자.

 

 

1. 시간 초과난 코드는 중복된 값을 제거할 때 contains()를 써서 빅오가 O(n^2)이 된다. 위에 있는 정답 코드처럼 중복된 값을 제거할 때 HashSet을 써서 중복된 값을 제거해야 빅오가 O(n)이 된다.

 

2. 시간 초과난 코드는 출력값을 생성할 때 indexOf()를 써서 빅오가 O(n^2)이 된다. 위에 있는 정답 코드처럼 HashMap을 생성하여 get()를 사용해 찾아야 빅오가 O(n)이 된다.