백준 1138번 한 줄 서기(Python, C++)

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

1138번: 한 줄로 서기

 

키가 작은 사람부터 result에 넣고 0의 갯수로 자신보다 키 큰 사람이 왼쪽에 몇 명 있는지 파악한다.

 

<python>

n = int(input())
c = list(map(int, input().split())) # 2100
result=[0 for i in range(n)] # 0000
for i in range(n):
    a = c[i] 
    cnt = 0
    for j in range(n):
        if cnt == a and result[j] == 0:
            result[j] = i+1
            break
        elif result[j] == 0:
            cnt += 1

for p in result:
    print(p, end=' ')

 

 

입력 4 / 2 1 1 0 이라면 1번은 왼쪽에 자기보다 키 큰 사람이 2명, 2번은 1명, 3번은 1명, 4번은 0명이다.

출력할 답을 Vector로 선언하고 키카 큰 순서대로 줄을 세운다. 

4번 사람(키가 제일 큰 사람)은 왼쪽에 자기보다 큰 사람이 0명이므로 일단 0번 index에 insert한다. (사실 4번은 어디에 있어도 자신이 가장 크므로 상관없다. 그래서 일단 0번에 넣어놓고 다른 사람들이 들어올 때 필요하다면 뒤로 가면 된다.)

Vector : 4

 

3번 사람은 1명이므로 1번 index에 insert한다.

Vector : 4 3

 

2번 사람은 1명이므로 1번 index에 insert한다.

Vector : 4 2 3

 

1번 사람은 2명이므로 2번 index에 insert한다.

Vector : 4 2 1 3

 

<C++>

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

vector<int>solve;
int c[10];

int main(void) {

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}

	for (int a = n-1; a >= 0; a--) {
		vector<int>::iterator iter = solve.begin();
		for (int b = 0; b < c[a]; b++) {
			iter++;
		}
		solve.insert(iter, a + 1);
	}
	
	for (int j = 0; j < solve.size(); j++) {
		cout << solve[j] << " ";
	}
	return 0;
}