[백준] 10989: 수 정렬하기 3

GitHub: https://github.com/tyt0815

tyt0815 - Overview

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

10989번: 수 정렬하기 3

수 정렬하기

브론즈 문제에 계속해서 가르침을 얻고 있습니다... 그냥 평범한 정렬로 접근해서 머지소트도 해보고 메모리 초과에 버블소트도 하였지만 역시나 메모리 초과가 났습니다. STL에 있는 sort함수를 사용해도 마찬가지로 메모리 초과가 납니다. 저번 문제와 비슷하게 입력에 함정이 있습니다. 입력에 대한 조건을 보면 다음과 같습니다.

여기서 핵심은 입력의 개수는 크지만 입력된 수는 10000이하로 작습니다. 이 말의 의미는 수가 중복해서 들어온다는 점과, int형 배열로 10,000,000개를 생성해서 메모리 초과가 난다는 점입니다.

 

저는 다음과 같이 풀었습니다.

• 길이가 10001인 배열을 만듦(0 ~ 10000). 그리고 0으로 초기화
• N을 입력받고, N번 수를 입력받음
• 입력 받은 수에 해당하는 배열에 +1을 더해줌.
• 배열에 기록된 수만큼 해당 인덱스를 출력해줌

#include <iostream>

using namespace std;

int main()
{
    uint32_t n, in;
    uint32_t ary[10001] = {0};

    uint32_t minN = 10001, minxN = 0;
    
    cin >> n;
    for(uint32_t i = 0; i < n; ++i)
    {
        cin >> in;
        ++ary[in];
        minN = min(minN, in);
        minxN = max(minxN, in);
    }
    for(uint32_t i = minN; i <= minxN; ++i)
    {
        for(uint32_t j = 0; j < ary[i]; ++j) { cout << i << '\n'; }
    }
    return 0;
}

여기서 최대 최솟값을 기록했는데, 필요없는 배열탐색을 줄이기 위해서 입니다.

 

참고로 이 코드로 제출하면 통과가 될 수도 있고 시간 초과가 될 수도 있습니다.