[C++] BOJ(백준) 1138 한 줄로 서기

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

 

사실 이렇게 빨리 다시 코테 블로그를 작성하게 될 줄은 몰랐다.

오랜만에 하니 역시나 재밌고, 코드를 더더더더더 간결하게 작성하고 싶어진다.

 

구현 문제다.

나를 기준으로 왼쪽에 자신보다 큰 사람이 몇 명인지 순차적으로 입력이 들어온다.

이와 비슷한 고난도 문제들에서는 자신보다 큰 거나 작은 것이 아닌 그들끼리도 관계를 가진다.

그러나 이 문제는 나와의 관계만 파악하므로 쉽게 해결할 수 있었다.

 

입력의 크기가 굉장히 작기 때문에 효율적인 방법을 생각하지 않아도 해결할 수 있다.
작은 사람부터 배치할 것이기에 이후에 위치하는 사람들은 나보다 큰 사람이다.

따라서 1번부터 n-2번 까지는 왼쪽에서 부터 i+1번째 빈 칸에 위치하면 된다.

n-2번 까지 위치를 정하면 두 자리가 남게 되는데 이 때 n-1번째 값이 0이라면 n-1이 남은 자리 중 왼쪽을 차지한다.

n-1번째 값이 1이라면 왼쪽에 큰 사람이 한 명은 존재해야 하므로 남은 자리 중 오른쪽을 차지한다.

 

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

int n;
int arr[10];
int res[10];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < n - 2; i++) {
		int cnt = 0;
		for (int j = 0; j < n; j++) {
			if (res[j] == 0) cnt++;
			if (arr[i] == cnt - 1) {
				res[j] = i + 1;
				break;
			}
		}
	}

	vector<int> v;
	for (int i = 0; i < n; i++)
		if (res[i] == 0) v.push_back(i);

	if (arr[n - 2] == 0) res[v[0]] = n - 1, res[v[1]] = n;
	else res[v[1]] = n - 1, res[v[0]] = n;

	for (int i = 0; i < n; i++) cout << res[i] << " ";
}