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

문제 링크

1138번: 한 줄로 서기

 

풀이

1. answer 벡터를 0으로 초기화한다.
2. 작은 키부터 자리를 찾아가는데, 이렇게 하게 되면 answer의 0은 자기보다 큰 키가 될 것이다.(자기 이후에 찾게 될테니)
   1. answer를 돌면서 자기보다 큰 키면(answer[j] == 0) zeroCnt를 하나 더해준다.
   2. 그렇게 zeroCnt가 arr[i]와 같아지게 되면 해당 자리의 다음 자리에 넣어주면 된다.
   3. 그 자리가 비어있지 않다면(0이 아니라면) 빈 자리를 찾아 넣어준다.
3. answer를 출력한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    vector<int> answer(n, 0);
    for (int i = 0; i < n; i++) // 작은 키부터 시작
    {
        int zeroCnt = 0;
        int j;
        for (j = 0; zeroCnt < arr[i]; j++) // 자기보다 큰 키(0) 수 세기
        {
            if (answer[j] == 0) zeroCnt++;
        }
        while (answer[j] != 0) // 해당 자리가 비어있지 않으면 다음 자리로
        {
            j++;
        }
        answer[j] = i + 1;
    }

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