[백준/C#] 10989 - 수 정렬하기 3

1. 문제

N개의 자연수를 오름차순으로 정렬하는 문제이다.

 

- 입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

- 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

- 설명 : 수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

 

메모리 제한이 8MB, 시간제한이 5초이다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
5 초	8 MB	261990	61617	46969	23.629%

예제 입력	예제 출력
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

 

10989번: 수 정렬하기 3

---

2. 풀이

카운팅 정렬(Counting Sort, 계수 정렬)을 사용해서 풀어야 한다. https://ko.wikipedia.org/wiki/%EA%B3%84%EC%88%98_%EC%A0%95%EB%A0%AC

 

하지만 출력을 Console.WriteLine()으로 하면 시간이 초과되고,

string.Join으로 배열을 한 번에 출력하려고 하면 메모리가 초과된다.

그래서 검색해 본 결과 StringBuilder로도 해결이 안 되고, StreamWriter를 사용해야 한다.

 

using문 안에서 StreamWriter 객체를 생성해서 SteamWriter의 WriteLine()으로 출력하면 된다.

StreamWriter는 입출력 스트림을 전달받아 입출력을 하는 클래스라서, 콘솔 출력 스트림 Console.OpenStandardOutput()을 생성자에 전달해 객체를 생성하면 콘솔 입출력을 할 수 있다. (Console.OpenStandardOutput())

Console.WriteLine()으로 바로 출력하는 것보다 훨씬 빠르게 출력된다.

 

언어별 출력 속도 비교 - https://www.acmicpc.net/blog/view/57

이 사이트를 보면 Console.WriteLine은 출력속도가 꼴등이고, StreanWriter가 가장 빠른 것을 확인할 수 있다.

// 수 정렬하기 3
int N = int.Parse(Console.ReadLine());
int[] count = new int[10001];

for (int i = 0; i < N; i++) {
    int input = int.Parse(Console.ReadLine());
    count[input]++;
}

using(var print = new StreamWriter(Console.OpenStandardOutput())) {
    for (int i = 0; i < count.Length; i++) {
        // count[i]에 저장된 수만큼 count[i]값을 출력.
        if (count[i] > 0) {
            for (int j = 0; j < count[i]; j++) {
                print.WriteLine(i);
            }
        }
    }
}

---

3. 배운 점

- 카운팅 정렬, 계수 정렬 : 

 

계수 정렬 - 위키백과, 우리 모두의 백과사전

주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 알고리즘이다.

 

간단하게 설명하면, 크기가 (주어지는 값의 최댓값+1)인 배열을 선언하고, 배열[입력값]++;으로 각 입력값이 몇 번 입력되었는지 세는 방법이다. 데이터 값과 동일한 인덱스에 저장된 값을 증가시키며 몇 번 등장했는지 저장하는 방식이다.

 

시간 복잡도는 O(n+k)이다. k가 주어지는 값의 최댓값이고, 음수가 아닌 정수이다.

https://visualgo.net/en/sorting 이 사이트에서 어떤 알고리즘인지 눈으로 확인할 수 있다. sort를 누르면 실행된다. 15.Counting Sort

- StreamWriter

https://learn.microsoft.com/ko-kr/dotnet/api/system.io.streamwriter?view=net-7.0

StreamWriter 클래스 (System.IO)

특정 인코딩의 문자 출력을 위해 디자인된 클래스라고 한다. using 문 안에서 사용하는 것이 좋다.

 

StreamReader, StreamWriter는 파일을 읽고 쓰는 데 사용하는데, 이번 문제에서 사용한 것처럼 WriteLine()으로 콘솔창에 출력하는 것도 가능하다. StreamWriter 객체 생성할 때 콘솔 출력 스트림을 전달하고 생성하면 된다.

 

생성자 - SteamWriter(Stream stream)

코드

var print = StreamWriter(Console.OpenStandardOutput());

print.WriteLine(내용);

 

- Console.OpenStandardOutput()

https://learn.microsoft.com/ko-kr/dotnet/api/system.console.openstandardoutput?view=net-7.0

Console.OpenStandardOutput 메서드 (System)

표준 출력 스트림을 반환한다.

OpenStandardOutput()	표준 출력 스트림을 가져옵니다.
OpenStandardOutput(Int32)	표준 출력 스트림을 가져와 지정한 버퍼 크기로 설정합니다.

https://learn.microsoft.com/ko-kr/dotnet/api/system.console?view=net-7.0

Console 클래스 (System)

 

- 출력 속도 비교

 

출력 속도 비교