[C++] 백준 10989번 수 정렬하기 3

1. 문제이해

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

10989번: 수 정렬하기 3

 

N개의 정수가 주어질 때, 이를 오름차순으로 정렬하여 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

이전 포스팅인 2750번 수 정렬하기, 2751번 수 정렬하기 2 문제와 거의 동일한 문제이다.

앞선 두 문제와의 차이점이 있다면, 입력받는 수의 범위가 10,000,000 라는 점이다.

앞선 두 문제는 C++의 내장함수인 sort 함수를 이용해 정렬해도 문제가 없었지만,

이번 문제는 입력받는 수의 범위가 크기때문에, 무작정 입력을 받아 정렬을 하게 되면 시간초과가 발생하게 된다.

 

그렇다면, 어떤 방법을 사용해야할까?

문제를 보면, 입력받는 숫자의 개수는 최대 10,000,000 개지만,

모든 수는 10,000 보다 작거나 같은 자연수임을 알 수 있다.

이 점을 이용하면, 입력받은 숫자들은 모두 10,000보다 작거나 같은 자연수이므로,

크기가 10,001인 배열을 지정해, 1~10,000 까지의 숫자가 몇번 나왔는지를 저장,

앞에서부터 해당 숫자가 나온 횟수 만큼 출력해주기만 하면 된다는 것이다.

(10,000까지의 숫자를 입력받을 수 있기 때문에, 배열의 크기를 하나 높여 10,000까지 셀 수 있도록 설정)

아래 예제를 통해 다시 한번 살펴보자.

 

 

ex)

5, 50, 3, 2, 6, 5 라는 숫자를 입력받은 경우,

크기가 10,001인 배열 num을 두어, 각 숫자가 나온 횟수만큼 숫자의 해당하는 배열 값을 증가시킨다.

(num[5] 의 값을 2 증가, num[50], num[3], num[2], num[6] 의 값을 1 증가시킨다.)

입력이 끝나면 num[0] ~ num[10001] 까지 배열의 값이 0이 아닌 것들을 찾고,

해당 배열의 값이 0이 될때까지 출력을 반복한다.

(num[5]의 값이 최초로 0이 아닌 값. 2이므로, 5를 한번 출력 후 1로 줄인다.

1이어도 0이 아니므로, 5를 한번 더 출력 후 0으로 줄인다. 값이 0이 되었으므로 다른 0이 아닌 값을 찾는다.)

 

 

이러한 알고리즘을 통해 작성한 코드는 아래와 같으며,

비슷한 문제로는 2750번 수 정렬하기, 2751번 수 정렬하기2 가 있다.

해당 문제들에 대한 풀이와 소스코드는 아래 포스팅을 참고하자.

 

<2750번 수 정렬하기>

https://beginnerdeveloper-lit.tistory.com/105

[C++] 백준 2750번 수 정렬하기

 

<2751번 수 정렬하기 2>

https://beginnerdeveloper-lit.tistory.com/106

[C++] 백준 2751번 수 정렬하기 2

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

// 해당 숫자가 몇번 나왔는지를 저장하는 배열
// 모두 0으로 초기화 한 뒤 시작
int num[10001] = { 0, };   

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cout.tie(NULL);

	int N;                    // 수의 개수
	int input_num;
	cin >> N;

	// 수를 입력받고, 숫자에 해당하는 배열 값을 증가시킨다.
	for (int i = 0; i < N; i++) {
		cin >> input_num;
		num[input_num]++;
	}

	// 10,000까지의 배열의 숫자 중 0이 아닌 것을 찾고,
	// 0이 아닌 것이 있으면 해당 배열값이 0이 될때까지 출력
	for (int i = 0; i <= 10000; i++) {
		while (num[i] != 0) {
			cout << i << "\n";
			num[i]--;     // 출력했으니, 값을 하나 줄여줌
		}
	}

	return 0;
}

2. 문제풀이에서 사용한 알고리즘을 이용해 작성한 코드는 위와 같다.

숫자가 몇번 나왔는지를 체크하는 배열 num을 두고, 수를 입력받아 해당하는 배열값을 증가시킨다.

이후 10,000까지의 숫자 중 0이 아닌 값이 있으면,

해당 배열값이 0이 될때까지 출력하고, 값을 줄이는 것을 반복한다.

 

주석 없는 코드는 바로 왼쪽 아래의 더보기 확인 바랍니다.😊

<주석 없는 코드>

#include <iostream>
using namespace std;

int num[10001] = { 0, };   

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cout.tie(NULL);

	int N;                   
	int input_num;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> input_num;
		num[input_num]++;
	}

	for (int i = 0; i <= 10000; i++) {
		while (num[i] != 0) {
			cout << i << "\n";
			num[i]--;     
		}
	}

	return 0;
}

 

 

 

---

사실 앞 두 문제는 이 문제를 위한 기초적인 문제였다.😊

앞 두 문제는 sort 함수만 사용하면 쉽게 풀리는 문제였고,

이번 문제는 크기가 워낙 큰 탓에 새로운 방법을 찾아내야 했는데,

이런 방법이 있구나~ 라는 것도 깨닫게 해준 좋은 문제였다고 생각한다.

(사실 이러한 풀이방법을 쓰기에는 제한이 좀 있기는 하다. 음수는 입력받지 않아야 된다던지 하는..)

 

질문과 지적은 언제나 감사히 받고있습니다.😌