문제 출처

1. 문제설명

  • N명의 사람들이 매일 아침 한 줄로 선다.
  • 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지 기억한다.
  • 키는 전부 다르다.
  • 각 사람이 기억하는 정보가 주어질 때 줄을 어떻게 서야하는지 출력하라.



2. 알고리즘 설계

  • 처음 이 문제를 보았을 때 같은 숫자가 입력으로 주어져서 당황했다.
    • 예제 1번을 보면, [2, 1, 1, 0] 이다.
  • 이 말은 즉슨, 줄을 설 때마다의 정보라는 것이다.
    • 다시 말해 2인 값은 0번째 사람이 자리에 섰을 때 왼쪽에 2명이 있었다는 것이다.
  • 이 부분을 고려하여, 값을 입력받을 때마다 자리를 찾아주면 된다.



3. 로직

  • 자신보다 키 큰 사람의 수를 입력받는다.
  • 자신의 자리를 찾아 갱신한다.
    • 만약, 자리가 이미 차 있다면, 오른쪽으로 한 칸 옮긴다.
    • 오른쪽으로 한 칸 옮겨 비어있다면, 그 자리로 들어간다.
    • 아니라면, 위 과정 반복
  • 2중 for-loop를 사용해 자신의 자리까지 입력값을 감소시킨다.
    • 예를들어, 2가 들어왔다면, input을 2만큼 깎아주면서,
    • 동시에 자신이 들어갈 자리 index j는 2만큼 증가시킨다.
    • input이 0이 되고, j번째 위치에 도달했다.
      • j번째가 이미지 차지되지 않았다면, 그 자리이다.
      • 아니라면, 오른쪽으로 한칸 옮긴다.
        • 즉 j만 증가시킨다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

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

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

	for (int i = 0; i < n; i++) {
		int tmp; cin >> tmp;

		for (int j = 0; j < n; j++) {
			if (tmp == 0 && arr[j] == 0) {
				arr[j] = i + 1;
				break;
			}
			else if (arr[j] == 0) tmp--;
		}
	}

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

	return 0;
}