boj 10989 수 정렬하기 3 C++

boj 10989 수 정렬하기 3 c++

백준 10989 수 정렬하기 3 cpp

 

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

 

9개월 전 c언어 배울 때 풀었어도 풀었을 문제...

정답 비율이 약 22%인 것을 보고 괜히 어렵게 생각했다가 다른 사람의 코드를 보고 나서야 한숨을 내쉬며 엄청 쉬운거였네 싶었다.

 

메모리 제한이 8mb이기 때문에 int를 10,000,000개 배열로 잡아도 40mb가 되기 때문에 배열에 먼저 넣는 것은 불가능하다.

하지만 들어오는 숫자의 최대값은 10000이므로 10000개짜리 배열만 선언해도 풀리는 문제이다. 왜냐하면 array의 [n]번째가 나올 때마다 ++시켜주고 출력시키면서 하나씩 감소시키면 되기 때문이다.

아래는 정답코드.

 

#include <bits/stdc++.h>
using namespace std;

int arr[10001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, tmp;
    cin >> n;
    while (n--)
    {
        cin >> tmp;
        arr[tmp]++;
    }
    int i = 1;
    while (i < 10001)
    {
        if (arr[i])
        {
            cout << i << '\n';
            arr[i]--;
            continue;
        }
        i++;
    }
    return (0);
}