[ 백준 ] 10989 수 정렬하기 3

codesver·2022년 11월 28일
0

Baekjoon

목록 보기
45/72
post-thumbnail

Solution

알고리즘 자체는 크게 어려운 문제는 아니다.

다만, 메모리 제한을 주의해야 한다는 것이 이 문제의 핵심이다.

기존의 코드는 다음과 같다.

private static void solution() throws IOException {
    Queue<Integer> queue = new PriorityQueue<>();
    int repeat = Integer.parseInt(reader.readLine());
    while (repeat-- > 0) queue.add(Integer.parseInt(reader.readLine()));
    while (!queue.isEmpty()) result.append(queue.poll()).append("\n");
}

우선 순위 큐를 통해 삽입 시 자동 정렬을 하고 차례대로 출력하는 알고리즘이다.

위의 알고리즘은 문제가 없지만 모든 입력값을 저장하는 곳에서 메모리가 초과되었다.

이를 해결하기 위해 입력값을 저장하는 것이 아니라 counter를 활용하여 작성하였다.

private static void solution() throws IOException {
    int[] counter = new int[10000];
    int repeat = Integer.parseInt(reader.readLine());
    while (repeat-- > 0) {
        int num = Integer.parseInt(reader.readLine());
        counter[num - 1]++;
    }
    for (int i = 0; i < counter.length; i++) {
        int count = counter[i];
        result.append(((i + 1) + "\n").repeat(count));
    }
}

위의 방법으로 해결하면 입력값들이 굉장히 많더라도 최대 10,000개(입력값 범위)만 저장한다.

이후 counter에 저장된 count 수에 맞게 index를 활용하여 출력하면 된다.

profile
Hello, Devs!

0개의 댓글