[BOJ] C++ 10431: 줄세우기 - 시뮬레이션은 문제를 잘 읽자!

10431번: 줄세우기

예제

4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919

ans :
1 0
2 190
3 19
4 171

---

문제 분석을 좀 해보자.

1. 자기보다 큰 사람이 앞에 있는지 체크해야 한다.
   • 완전 탐색으로 O(N)만큼 걸린다.
2. 자기보다 큰 사람이 있다면 그중 제일 앞에 있는 학생 앞에 선다.
   • 학생 앞에 서고 테이블을 갱신하는데 완전 탐색으로 O(N)이 걸린다.
   • 답 계산에는 상수 시간이 걸린다.

이처럼 바로 시뮬레이션 풀이는 떠오른다. 1초 안에 해결이 될까? 학생의 수는 20명으로 고정이므로 한 테스트케이스당 400개의 연산만 발생한다. 테스트케이스도 1000개밖에 안되므로 무조건 1초 안에 해결이 가능하다 생각해서 문제에서 시키는 그대로 구현해 봤다.

 

여기서 주의할 점이 문제를 꼭 잘 읽고 차례대로 구현해야 효율적으로 풀린다는 것이다. 특히 시뮬레이션은 이런 문제가 많다.

 

나는 처음에 문제를 대충 읽고 풀어서 주어진 입력 그대로에서 맨 뒤 학생부터 줄 세우는 방식으로 풀었는데 아예 다른 풀이였다. 문제를 차근차근 읽어보면 아무나 한 명 뽑아서 맨 앞에 세우고 그 뒤로 줄 서는 한 명마다 규칙에 따라 줄 세우기를 하라고 한다.

 

물론 모든 학생을 세우고 idx = 1~19로 해서 줄을 세워도 되지만 그렇게 하면 

 

자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다.

이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.

 

이 문장이 굉장히 헷갈린다.

A B C D E F G 학생이 있다고 가정하자. 그리고 E학생이 B학생 앞으로 가야 한다면 B C D 학생만 뒤로 물러나야 하고 G 학생은 물러날 필요가 없다. 이런 헷갈리는 상황을 만들지 말고 문제에서 시키는 대로 한 명씩 입력받아서 줄 세우기를 하는 풀이가 덜 헷갈릴 것이다.

/** 시뮬레이션 10431 줄세우기 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

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

    int T;
    cin >> T;
    while (T--)
    {
        int idx, cnt = 0;
        cin >> idx;

        int arr[20];
        cin >> arr[0];

        for (int cur = 1; cur < 20; cur++)
        {
            // cur번째 학생이 줄 설 차례
            cin >> arr[cur];
            int taller_idx = -1;
            for (int front = cur - 1; front >= 0; front--)
                if (arr[front] > arr[cur])
                    taller_idx = front;

            if (taller_idx != -1)
            {
                // 자기보다 키 큰 학생을 찾은 경우
                // taller_idx부터 cur-1까지 학생들을 뒤로 한 칸 물리면 된다.
                int cur_h = arr[cur];
                for (int change = cur; change > taller_idx; change--)
                    arr[change] = arr[change - 1];
                arr[taller_idx] = cur_h;

                cnt += cur - taller_idx;
            }
        }
        cout << idx << ' ' << cnt << '\n';
    }
}