[백준 | 10867] 중복 뺴고 정렬하기- Java

📃 제출

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

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));

        int N = Integer.parseInt(br.readLine());
        
        boolean[] n = new boolean[2001];
        String[] s = br.readLine().split(" ");
        for (String str : s) {
            n[Integer.parseInt(str) + 1000] = true;
        }

        for (int i = 0; i < n.length; i++) {
            if(n[i])  {
                bw.write(i - 1000 + " ");
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

✏ 풀이

중복이라는 단어를 보았을 때 Set을 생각했지만, 배열로 문제를 해결하고자 했습니다. 문제에서 절대값이 1,000보다 작거나 같은 정수를 처리해야 하므로, -1,000부터 1,000까지를 포함할 수 있는 2,001 크기의 배열을 선언하였습니다. 이후 숫자를 배열의 인덱스에 맞춰 설정하고, 배열을 순회하며 배열에 true로 설정된 인덱스의 값을 출력하였습니다. 이 코드의 시간 복잡도는 $O(n)$입니다. 배열의 크기는 상수 크기이므로 배열을 순회하고 처리하는 시간은 상수 시간을 가지며, 문자열 s의 처리 시간만이 입력 크기 n에 비례합니다.