[백준 BOJ] 10989번 수 정렬하기 3 (C++/cpp)

문제 설명

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

10989번: 수 정렬하기 3

 

접근 방법 - 계수 정렬을 이용한 문제

백준의 10989번 문제는 계수 정렬을 이용하여 해결해야 하는 문제이다.

해당 문제는, 입력받은 숫자들을 오름차순으로 정렬하여 출력해야 하는 문제이다. 

여기서 계수 정렬에 대한 간략한 설명은 아래와 같다.

- 이는 배열의 성질을 사용하여 정렬을 수행하는 방법이다.
- 배열값은 배열 번호의 값이 나타난 총 빈도수를 나타낸다고 가정한다.
- 입력값들이 0 또는 양수여야 사용할 수 있는 방법이다.

해당 문제의 입력값들은 모두 양수이기 때문에, 계수 정렬을 사용하여 해결할 수 있는 문제이다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다. 

계수 정렬에 대한 자세한 설명도 함께 작성하니, 이 정렬이 어색하다면 아래의 설명을 참고하길 바란다.

 

코드의 실행 순서

1) 입력값들을 저장할 배열(cnt)을 전역변수로 선언한다.

 

2) 입력받을 숫자의 개수(n)를 입력받는다.

 

3) 숫자를 순차적으로 입력받으며 아래의 연산을 취한다.

- 입력값을 배열 번호로 갖는 각 cnt 값에 1을 더한다.

- 입력을 받으면서, 입력값들 중 최대값(max)을 구한다.

 

4) 입력을 마쳤다면, 이중 반복문을 만들어 아래와 같은 연산을 취하면서 출력을 실행한다.

- 배열 번호 0번부터 max번까지 cnt의 값을 탐색한다.

- 각 배열값만큼 배열 번호를 출력한다. (탐색하는 배열 번호의 값이 0이라면, 출력하지 않는다.)

 

5) 출력을 모두 끝냈다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 10989번 코드
int cnt[10001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	int input;
	cin >> n;
	int max = 0;
	for (int i = 0; i < n; i++) {
		cin >> input;
		cnt[input]++;
		if (max < input) { max = input; }
	}

	for (int i = 0; i <= max; i++) {
		for (int j = 0; j < cnt[i]; j++) {
			cout << i << endl;
		}
	}
}

 

제출 결과

(2022.03.21 백준 10989번 문제 제출 결과)