[백준] 1138

코드로 바로 가기
코드 구현력이 부족하다. 다시 기초부터.

풀이

줄 세우기 문제로, 중복없는 순차적인 키를 가진 각 사람들은 자신의 왼쪽에 선 사람 중 자신보다 키가 큰 사람의 명수를 저장합니다.
예시로 나온 입력은
4
2 1 1 0
으로, 4명의 사람이 있고, 키가 1인 사람은 자기보다 큰 사람 2명이 왼쪽에, 2인 사람은 1명이 왼쪽에, 3인 사람은 왼쪽에 1명, 4인 사람은 왼쪽에 0명이 있음을 의미합니다.
왼쪽에 n명이 있다는 것의 의미는 결국 ‘자신보다 키가 작은 사람을 제외했을 때 자신의 줄서기 순서가 n번째’임을 의미합니다.
이를 토대로 코드를 세웠습니다. arr배열은 줄 선 순서를 의미하며, 처음에는 아무도 줄에 서있지 않기 때문에 모든 노드에 -1을 할당해주었습니다.
이후 사람의 수를 받고, 수 만큼 for루프를 돌며 입력으로 주어진 ‘왼쪽에 선 사람 수’를 담는 p(people) vector를 만들어주었습니다.
이후 (0~N]만큼 이중 포문을 돌며, 줄에서 자신보다 큰 사람의 수가 p[i]가 될 때까지 이동(cnt++)합니다. p[i]가 되면(cnt == left_p) arr[j]에 할당하여 줄을 세워주었습니다.
입력과 출력을 제외하고 단순히 for문으로 추정한 시간복잡도는 O(N^2)이나 최악의 경우(늘 자신의 자리를 가장 마지막에 찾는 경우, 즉 4, 4 3 2 1 등 내림차순으로 들어오는 경우)에도 순차적으로 자리를 빨리 찾을 것입니다. 그러므로 시간복잡도는 O(NlogN)입니다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;
int arr[11];

int main()
{
	for (int i = 0; i < 11; i++) arr[i] = -1;
	int N = 0;
	cin >> N;
	vector<int> p;
	for(int i=0;i<N;i++) {
		int n;
		cin >> n;
		p.push_back(n);
	}
	for (int i = 0; i < N; i++) {
		int left_p = p[i];
		int cnt = 0;
		for (int j = 0; j < N; j++)
			if (arr[j] == -1) {
				if (cnt == left_p) arr[j] = i + 1;
				cnt++;
			}
	}
	for (int i = 0; i < N; i++) cout << arr[i] << ' ';
	return 0;
}