[C++][백준 1138] 한 줄로 서기

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

풀이

키가 1인 사람부터 시작한다면 이후에 오는 사람들은 전부 본인보다 큰 사람들일 것이기 때문에 주어진 수(자기보다 키가 큰 사람이 왼쪽에 몇 명 있었는지)만큼 왼쪽이 비어 있어야 한다

 

주어진 수만큼 왼쪽을 비운 다음에 본인이 들어가면 되는데, 이미 앞서 들어간 사람이 있는 경우 들어갈 자리가 있을 때까지 오른쪽으로 이동한다(오른쪽으로 계속 이동해도 본인보다 앞서 들어간 사람은 전부 본인보다 작으므로 상관없다)

 

제출 코드

#include <iostream>
using namespace std;

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

    int n;
    cin >> n;
    int arr[10] = {};

    for (int i = 1; i <= n; i++)
    {
        int input, count = 0;
        int pnt = 0;
        cin >> input;
        while(count < input)
        {
            if (arr[pnt] == 0)
                count++;
            pnt++;
        }
        while(arr[pnt] != 0) pnt++;
        arr[pnt] = i;
    }

    for (int i = 0; i < n; i++)
        cout << arr[i] << ' ';
}