[백준] 2751번 - 수 정렬하기 2 [Java]

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

 

[백준] 2751번 - 수 정렬하기 2 [Java]

---

1.  아이디어

 

일반적인 sort 정렬로는 시간초과가 발생할 수 있다.

수가 중복되지 않고 수의 범위가 주어져 있으며 범위가 넓지 않다는 점에서 카운팅 정렬을 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

수가 중복되지 않으므로 등장 유무만 판단하면 된다. 이를 위해 boolean 타입의 배열을 활용해서 등장한 수에 해당하는 인덱스의 원소만 true로 바꿔주고 이후 배열을 순회하며 등장한 원소의 인덱스를 출력하는 방식으로 구현했다. 음수도 등장할 수 있으므로 이에 대한 보정은 해줘야 한다.

---

3. 코드

 

import java.io.*;

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

        final int MAX = 1_000_000;
        boolean[] visited = new boolean[MAX + 1 + MAX];
        for (int i = 0; i < N; i++) {
            visited[Integer.parseInt(br.readLine()) + MAX] = true;
        }

        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) sb.append(i - MAX).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기