[백준] 수 정렬하기 3_ 10989_자바

10989 Java - 수 정렬하기 3

---

이번 문제는 <정렬> 카테고리에 해당하는 [수 정렬하기 3] 입니다. 문제의 입출력을 보았을 때는 그렇게 어려운 문제는 아닙니다. 하지만 메모리와 시간제한이 타 문제보다 까다로운데요. 이 때문에 저도 문제를 풀면서 많은 고민을 하게 되었습니다.

 

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

10989번: 수 정렬하기 3

---

백준 - 정렬 - 수 정렬하기 3

입력과 출력 예시

---

풀이

---

 

 

수 정렬하기3 문제를 딱 보자마자, 다양한 정렬 알고리즘을 사용하여 풀면 되겠다고 생각했습니다. 하지만 생가보다 메모리와 시간제한이 크게 까다로웠습니다.

• (Java) 시간 제한 3초
• (Java) 메모리 제한 512MB

이제는 정렬 알고리즘을 완전히 능숙하게 안다고 생각했으나, 위와 같은 결과를 받고 굉장히 당황스러웠습니다..

아마 저와 같은 결과를 얻는 사람이 많을 것으로 예상됩니다. 이제 풀이를 알아보도록 하겠습니다.

 

---

1) 첫 번째  풀이

---

Arrays.sort 활용

BufferedReader + StringBuilder

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

public class SortNum3_10989_5 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

	    // 입력할 수 개수 입력
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];

	    // 입력한 값들 배열에 선언
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

	    // 정렬
        Arrays.sort(arr);

	    // StringBuilder를 통해 배열의 값들을 하나의 문자열로 만듦
        for (int data : arr) {
            sb.append(data).append('\n');
        }

        System.out.println(sb);
    }
    
}

 

위 코드의 결과

Arrays 클래스의 sort() 메서드를 활용하고, StringBuilder를 통해서 출력한 방법입니다. 보다시피 정답인데요.

사실 그렇게 어려운 문제가 아녔습니다. 단순히 Arrays.sort()를 사용하면 되는 문제였습니다.

그렇다면 그 전에는 무엇이 문제였을까요?

처음 시도는 ArrayList로 만들고, Collections.sort()를 사용하여 위와 동일하게 진행했습니다. 하지만 메모리 부족이라는 판정을 받았습니다. 따라서 컬렉션 프레임 워크를 사용하면 안 된다는 인사이트를 얻게 되었습니다.

위 코드에서 추가 포인트는 입력 시에는 BufferedReader, 출력은 StringBuilder를 활용했다는 점입니다. 입력 시에 Scanner를 사용하는 것보다 BufferedReader를 사용하는 것이 빠르다는 것은 전에 문제를 풀면서 알았습니다. 이제 출력을 보겠습니다. 보통은 향상된 for문 안에서 System.out.println(data)을 사용해도 큰 문제는 없었습니다. 하지만 이번 문제에서는 이와 같이 출력하면 시간 부족이라는 결과를 얻게 됩니다. 이유는 배열 안을 모두 순회하면서 System.out 메서드를 계혹 호출하기 때문입니다. 가령 데이터가 10,000개라면, 10,000번을 호출하는 것이죠. 따라서 StringBuilder를 통해서 출력할 값들을 모두 연결하고, 만들어진 하나의 문자열을 한번 출력하게 만듭니다. 덕분에 시간 부족이라는 에러를 피할 수 있게 됩니다.

결론은 Arrays.sort와 StringBuilder 등으로 아슬아슬하게 통화하게 됩니다.

Arrays.sort() 의 경우 dual-pivot Quick sort 알고리즘 사용
평균 O(nlogn) ~ O(n^2) 시간 복잡도 발생

---

2) 두 번째 풀이

---

카운팅 정렬 알고리즘 활용

import java.io.*;

/**
 * Point
 * 1) 컬렉션 프레임워크를 활용하면 메모리 부족 발생
 * 2) 카운팅 정렬 활용
 * 3) 입력 범위 10,000 이하 활용
 *
 * 수행시간 1624ms
 */
public class SortNum3_10989_4 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        // 입력되는 값이 10,000 이하,
        // 입력받은 값을 인덱스로 사용
        int[] input = new int[10001];

        for (int i = 0; i < N; i++) {

            // 입력 받은 값과 동일한 인덱스에 +1
            input[Integer.parseInt(br.readLine())]++;
        }

        br.close();
        StringBuilder sb = new StringBuilder();

        for(int i =0; i < input.length; i++) {

            // 해당 인덱스에 값이 0이 될때가지 1씩 감소하며, 반복
            while(0 < input[i]--) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }
}

 

문제에서 제시된 내용을 보면, 아래 이미지처럼 수가 10,000 이하의 정수라는 것을 알 수 있습니다.

 

따라서 처음부터 크기가 10,001인 배열을 만들어줍니다. 풀이는 해당 배열의 인덱스를 활용합니다. 처음 입력한 N 만큼 반복문을 순회하는데요. 즉, N개의 정수를 입력하는데, 정수를 입력할 때 해당 인덱스에 값을 1씩 증가하게 됩니다.

위 코드에서 적용되는 정렬 예시

만약 [ 2, 9998, 3, 3, 10000 ]을 입력했다고 하면, 아래 그림처럼 input 배열에 값이 들어가게 되는 것입니다.

위와 같이 모든 값에 맞도록 각 인덱스에 적용이 되었다면, 이제 이 배열에서 값을 출력합니다. 다음 for문을 진행하는 것이죠.

for 문은 배열의 0번(또는 1번)부터 10000번까지 순회합니다. 도중에 값이 존재한다면, while문을 통해서 값이 0이 될 때까지 해당 인덱스를 문자열에 연결해줍니다. (StringBuilder로 append)

그림의 값으로 예시를 들면, 인덱스 2번에 1이란 값이 있기 때문에 값은 -를 하고, 2 인덱스를 append 합니다. 3번 인덱스에서는 2가 0이 되기 위해서 두번 반복을 진행하고, 3번 인덱스가 두 번 append 하게 됩니다. 이러한 방법으로 카운팅이 되는 것이죠.

그리고 마지막에는 2, 3, 3, 9998, 10000 로 정렬되는 것을 알 수 있습니다.

---

결론

---

두 번째에서 푼 방법은 시간 복잡도가 O(N) 발생합니다.

지금까지 백준 문제를 풀어보았을 때, 배열의 인덱스를 활용하는 풀이 방법을 많이 사용했습니다.

꼭 잊지 않고, 다른 문제에서도 활용할 수 있도록 기억!!