한 줄로 서기 (백준 - 1138번)

그리디 알고리즘을 사용하는 문제였다.

 

입력에서 키 정보와 자신보다 키가 큰 사람이 왼쪽에 몇 명이 있는지에 대한 정보가 주어진다. 그렇게 때문에 줄을 어떻게 서야 하는지에 대한 정보를 저장할 배열 result를 만들어 놓고 가장 작은 키의 사람부터 정보에 맞게 result에 키를 나열해주면 된다.

 

사람의 수는 10을 넘기지 않으므로 키의 범위는 1~10이 될것이다. 이 범위를 넘어가는 11을 빈자리로 선언하고 result를 빈자리로 채워넣는다.

 

위의 예제를 예로들어 설명하겠다. 사람 4명이 있으므로 result 배열의 크기는 4일 것이다.

 

둘째 줄 입력에 정보를 바탕으로 result에 줄의 순서를 배치해보자. 

우선 키 1인 사람은 자기보다 키큰 사람이 왼쪽에 2명이 있다. 그러므로 자신의 키보다 큰 EMPTY를 2번 건너 뛰고 3번째 자리 자리가 EMPTY이기 때문에 그 자리에 배치가 될것이다. 

 

그리고 키 2인 사람은 자기보다 키큰 사람이 왼쪽에 1명이 있다. 역시 자신의 키보다 큰 EMPTY를 1번 건너 뛰고 2번째 자리가 EMPTY이기 때문에 그 자리에 배치가 된다.

 

키 3인 사람은 자기보다 키큰 사람이 왼쪽에 1명이 있다. 자신의 키보다 큰 EMPTY를 1번, 그리고 자신보다 작은 키의 2와 1을 건너 뛰어 맨 마지막 4번째 자리가 EMPTY이기 때문에 그 자리에 배치가 된다.

 

그리고 마지막으로 키 4인 사람은 자기보자 키큰 사람이 왼쪽에 없다. 그러므로 건너뛸 필요없이 첫번째 자리가 EMPTY이므로 그 자리에 배치가 된다. 

 

코드로 표현하면 다음과 같다.

#include <iostream>
using namespace std;

const int EMPTY = 11;

int main()
{
	int N;
	cin >> N;
	
	int* person = new int[N];
	int* result = new int[N];
	for (int i = 0; i < N; ++i)
	{
		cin >> person[i];
		result[i] = EMPTY;
	}

	for (int i = 0; i < N; ++i)
	{
		int count = 0;
		int leftCount = person[i];
		int personHeight = i + 1;

		for (int j = 0; j < N; ++j)
		{
			if (leftCount <= count &&
				result[j] == EMPTY)
			{
				result[j] = personHeight;
				break;
			}
			if (result[j] > personHeight)
				++count;
		}
	}

	for (int i = 0; i < N; ++i)
	{
		cout << result[i] << " ";
	}
	cout << endl;

	delete[] person;
	delete[] result;
}