c++ 10989번 문제. 메모리 제한이 아주 작은 문제는 평소와 다른 방식을 원한다는걸 고려해보자.

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

10989번: 수 정렬하기 3

 

수 정렬 문제를 연달아 풀고 있는데, 

수 정렬하기

수 정렬하기 2

수 정렬하기 3

1번과 2번은 문제없이 stl sort로 바로 해결이 되는데, 3번째 문제는 시간 제한이 매우 길게 설정되어있고, 

메모리 제한이 그동안 보던 문제들에 비해서 아주 작게 설정되어있다. 

1번 문제의 경우 시간제한 1초, 메모리 제한 128mb

2번 문제의 경우 시간제한 2초, 메모리 제한 256mb

그런데 3번 문제의 경우 시간제한 5초, 메모리 제한 8mb이다. 

시간제한을  아주 크게 늘려놓고, 메모리 제한을 아주 작게 만들어버렸다.

그러니까 이 제한을 보았을때, 메모리를 굉장히 절약해서 쓰면서 문제를 풀어야 하지만, 연산하는데 걸리는 시간은 넉넉하게 만들어주겠다는걸 생각해야 할것같다. 

 

그래서 뭔가 내가 알지 못하는 무엇인가가 있을것 같아서 문제를 틀리자 마자 검색해보았는데, 굉장히 이해하기 쉽게 정리가 잘 되어있는 블로그 글을 발견하였고, 내용 자체는 카운팅 방법을 활용해서 해결하는거라 충분히 생각해서 해결 할 수 있었을 문제라는 생각이 든다. 

 

https://tooo1.tistory.com/72

[백준(BOJ)] 10989번 : 수 정렬하기 3 - C++[CPP]

 

#include <iostream>

using namespace std;

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

    int N;
    cin >> N;

    int input[10001] = { 0 };

    for (int i = 0; i < N; i++) {
        int in;
        cin >> in;
        input[in] += 1;
    }

    for (int i = 1; i < 10001; i++) {
        for (int j = 0; j < input[i]; j++) {
            cout << i << '\n';
        }
    }
}

원래 코드에서는 cout.tie(null)도 있었는데, 필요없다고 판단하여서 제거하였다.

카운팅 방법을 한번 고려해볼만 했을것 같은데, 너무 바로 내가 모르는 방법이라고 고려한것이 아쉽게 느껴진다.

수 정렬하기 세가지 버전을 다 돌아보면서 한번 3번째 문제를 만났을때 다시 올바른 방향으로 갈 수 있도록 문제를 보고 시간제한과 공간제한을 바라본뒤에 그 정보를 문제를 푸는데 활용하는 습관을 들이도록 하자. 

 

처음에 해결하려던 방법으로 

int num[10'000'005]; 형태로 잡아버리면,

이게 40,000,000바이트이고, 이건 40mb바이트에 해당한다. 문제에서 제시한 메모리 제한은 8mb바이트 이기 때문에 완전 벗어나게 된다. 

이런걸 염두해 두면서 애초부터 변수를 잡을때 대략적으로라도 머리속에서 계산해서 이게 메모리 제한을 넘지 않는지 고려해보도록 하자.