백준 10989 문제풀이

문제 링크

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

문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

문제 분석

카운팅 배열을 사용하여 각 숫자의 빈도를 저장한다 -> 카운팅을 할 배열을 생성. 여기서 cnt[number]는 해당 숫자가 입력된 횟수를 저장한다. 그 후, 1부터 10,000까지 차례대로 탐색하면서 cnt[i] 값이 0보다 크면, 숫자 i를 빈도만큼 출력.

코드

#include<bits/stdc++.h>
using namespace std;
int cnt[10001];
int number;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> number;
        cnt[number]++;
    }
    for(int i = 1; i <= 10000; i++){
        while(cnt[i]-- > 0){
            cout << i << '\n';
        }
    }
    return 0;
}

단순히 누적된 카운팅 값을 모두 1부터 10000까지 순회하면서 인덱스 출력 한가지 주의점은 처음에 입력값을 vector로 받았을 땐 입력값이 너무 커서 메모리 초과가 발생했음..

Reference

나의 뇌