[백준]1138번 한 줄로 서기

 

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

1138번: 한 줄로 서기

문제

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

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

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

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

---

입력은 키순서 대로 있으며 자신의 왼쪽에 자신보다 큰 사람의 수를 나타내고 있다.

결국 실제로 서 있는 순서를 나타내는 배열(line[ ])을 활용하여 내 앞에 큰사람들의 자리를 남겨두고 자신의 자리를 찾아가면 된다. jump 라는 변수를 활용해서 현재 확인하는 사람의 왼쪽에 몇명이 있는지 저장을 하고 시작한다. line 배열을 순회하면서 나보다 큰 사람을 위한 자리를 남겨두고 jump 값을 감소시키며 자신의 자리를 찾아간다. jump의 값이 0이 될 때가 자신의 자리이다. 이때 이미 자리가 차지된 경우는 어차피 나보다 작은 사람이니 내 왼쪽의 사람의 수에 영향이 없으니 jump를 감소하지 않고 건너뛴다. 

#include <iostream>

using namespace std;

int N;
int height[11];
int line[11] = { 0 };

void solve() {
	for (int i = 1; i <= N; i++) {
		int jump = height[i];
		int index = 0;
		while (1) {
			if (line[index]) {
				index++;
			}
			else {
				if (jump == 0) {
					line[index] = i;
					break;
				}
				else {
					jump--; index++;
				}
			}


		}
	}
	for (int i = 0; i < N; i++)
		cout << line[i]<< ' ';
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> height[i];
	}
	solve();

}

---

처음에 문제를 읽고 풀려고 하는데 어떻게 풀지 방법이 떠오르지 않았다. 그렇게 안 어렵게 보이는데 왜 생각이 안날까 하다가 문제의 조건 "i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다"라는 구문이 눈에 띄었다. 이게 무슨 뜻일까 고민했는데 다시 보니깐 주어진 입력은 "키가 1인 사람부터 차례대로"라고 적혀있었다.

처음에 읽었을때는 당연하다고 넘긴 것 같은데 문제를 풀려고 하니깐 생각을 못하고 어떻게 풀지만을 고민하고 있었다. 문제를 제대로 읽어서 주어지는 입력값의 의미를 잘 파악해야겠다고 느꼈다. 

또 문제를 다 풀고 블로그에 포스팅 할 그림을 그리던 중 원래는 코드에 visited 라는 배열을 따로 두었으나 visited를 굳이 활용할 필요 없이 line에 값이 들어 있으면 넘어가기 때문에 굳이 vistied 배열을 둘 필요가 없었다.

블로그 포스팅을 작성하면서 내 풀이를 정리하고 내 생각의 흐름을 다시 볼 수 있어서 좋은 것 같다. 내가 짠 코드인데 이걸 어떻게 설명해야하지라는 생각을 자주 했다. 코드를 일단 굴러가겠지하고 우선 대충 짜고 고쳐나가는 버릇이 있는 것 같다. 그래서 쉬운 문제들 조차 단번에 성공하면 내가 짠 코드지만 신기해 하는 경우가 많이 있다. 또, 코드를 무작정 작성하고 보니 조건을 계속 덧붙이는 경우가 많아 코드가 산으로 가거나 완성해도 코드가 덕지덕지 붙어있다는 느낌을 받을 때가 많았다. 이제부터는 코드에 손을 대기 전에 미리 제대로 구상을 하고 짜는 버릇을 들이면 좋을 것 같다.