C++ / 1138 / 한 줄로 서기 ( 그리디 알고리즘 )

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

문제 요약

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 섭니다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았습니다.

그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인합니다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억합니다.

N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다릅니다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성해야합니다.

문제 풀이

1. 사람의 수를입력 받습니다.

2. 사람 수 별로 앞에 자기보다 큰 사람 수를 입력받습니다.

3. 자기보다 큰 사람을 세어 줄 변수를 초기값 0으로, 입력할 숫자 ( 사람 )를 받을 변수를 1로 만듭니다.

4. 사람별로 입력받았던 자기보다 큰 사람 수 기준으로 자기보다 작은 사람은 무시하면서 비어있는 칸을 셉니다.

5. 비어있는 칸의 수가 자기보다 큰 사람수와 일치하면 정답 배열에 저장하고, 사람 수를 세는 변수를 0으로 만들고 입력할 숫자를 증가시킵니다.

6. 정답 배열을 출력합니다.

주의할 점

그리디 알고리즘은 푸는 과정이 재밌는 것 같습니다.

 

자기보다 작은 사람일 때 숫자를 세지 않도록 무시하는 것이 중요합니다.

코드

#include<iostream>
#include<vector>

using namespace std;

int n;
vector<int>v, ans;


int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}

	// 자기보다 큰 사람 
	int t = 0;
	// 입력할 숫자
	int b = 1;

	ans.resize(n);

	// 앞에 몇명 있는지
	for (int i : v)
	{
		for (int j = 0; j < n; j++)
		{
			// 자기보다 작은 사람일때 무시
			if (ans[j] > 0)
			{
				continue;
			}
			else
			{
				// 자기보다 큰사람 수가 일치 할 때
				if (t == i)
				{
					ans[j] = b;
					t = 0;
					b++;
					break;
				}
				else// 아직 자기보다 큰 사람 수가 안채워졌을때
				{
					t++;
				}
			}
		}
	}

	for (int i : ans)
	{
		cout << i << " ";
	}

	return 0;
}

반응형

예제 1

4
2 1 1 0

결과 1

예제 2

5
0 0 0 0 0

결과 2

예제 3

6
5 4 3 2 1 0

결과 3

예제 4

7
6 1 1 1 2 0 0

결과 4