BOJ. 10989

#BOJ10989

수 정렬하기 3

이런 시리즈 문제는 보통 셋 중에 하나는 항상 고장이 나있다. 티어, 메모리, 시간제한... 이 문제는 티어랑 메모리가 고장나 있어서 벌써 심상치가 않다. 근데 보통 이런 경우에는 티어를 믿으면 된다. 티어가 높으면 웬만하면 안된다. 티어가 낮으면 웬만하면 된다. 이런 생각을 바탕으로 문제를 풀기 시작하였다.(아 클래스2에 이전에 안 풀었던 몇 안되는 문제 중 하나였다. 추가로 정답률 23%(?) 뭔가 굉장히 악랄한 의도가 들어간게 분명하다...)

아래는 먼저 만든 소트를 이용한 날먹 코드다. 근데 역시 예상대로 메모리 초과가 뜬다.

# include "iostream"
# include "algorithm"
using namespace std;

int main(void){
    int N;
    cin >> N;
    int arr[N];
    for (int i = 0; i < N; i++){
        cin >> arr[i];
    }
    sort(arr, arr + N);
    for (int i = 0; i < N; i++){
        cout << arr[i] << endl;
    }
    return 0;
}

더 맘이 아픈건 어떻게 해결해야 될지 감도 안 잡힌다는거다.. 그래서 문제로 돌아가서 살펴보니 힌트를 얻을 수 있었다. 이 문항은 개인적으로 배울게 많은 문항이라는 생각이 든다. 우리가 평상시에 사용하는 소트 알고리즘에서 원소의 갯수를 제한한다면 이런식으로도 해결할 수 있겠구나 하는 생각이 들었다. 원소의 개수가 한정되어 있기 때문에 원소의 개수 만큼의 배열을 먼저 선언하였다. 그리고 각 원소의 수로 되어있는 부분에 인덱싱으로 접근하여 수를 늘려 주었다. 그래서 완성한 코드를 신나서 제출하였다. 하지만 놀랍게도 시간초과가 나왔다.

# include "iostream"

using namespace std;

int main(void){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    int arr[10001] = {0};
    for (int i = 0; i < N; i++){
        int temp;
        cin >> temp;
        arr[temp] ++;
    }

    for (int i = 1; i <= 10000; i++){
        while(arr[i] != 0){
            cout << i << endl;
            arr[i] --;
        }
    }
    return 0;
}

하지만 결과는 시간초과였다. 그러던 도중 동기의 조언으로 endl 대신 "\n"으로 넘겼고, "맞았습니다"가 나왔다... 백슬래시 고맙다.. 앞으로 endl은 내 사전에서 지워야 겠다.