(C++) - 백준(BOJ) 1138번 : 한 줄로 서기

www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

greedy 문제였습니다.

 

풀이방법

 1. 가장 작은 키의 사림이 위치한 곳은 자기가 왼쪽으로부터 떨어진 거리입니다. 왜냐하면 무조건 자기 보다 큰 사람이 왼편에 서기 때문입니다. 이를 착안한다면 n^2의 시간복잡도로 문제를 해결할 수 있습니다.

 

 2. 0의 개수를 세줍니다. 그래서 0의 개수가 i번째 사람의 키와 같고 비어있는 위치라면 바로 정답배열에 키의 값을 넣어줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n;
int a[11],ans[11];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        int cnt = 0;
        for(int j = 0; j < n; j++){
            if(a[i] == cnt) {
                if(!ans[j]) { ans[j] = i+1; break; }
            }
            else
                if(!ans[j]) cnt++;
        }
    }
    for(int i = 0; i < n; i++) cout << ans[i] << ' ';
}