[백준 BOJ / C++] 1138번: 한 줄로 서기

 

문제링크: www.acmicpc.net/problem/1138 

1138번: 한 줄로 서기

 

풀이

 

키가 작은 사람부터 몇 번째 자리에 서면 되는지 정했다. 정답 배열을 0으로 초기화한 다음, 자기보다 큰 사람이 왼쪽에 2명 있다면 3번째 자리에 서는 방식으로 문제를 해결했다. 작은 키 순서대로 확인하기 때문에 이미 정답 배열에 들어간 사람(줄을 선 사람)은 모두 자신보다 키가 작다고 생각할 수 있다. 

 

예제 입력처럼 [2, 1, 1, 0]이 입력으로 주어졌을 때 answer은 다음 순서로 계산된다. answer의 초기 상태는 [0, 0, 0, 0]이고, 줄을 선 순서대로 키를 저장한다. 

 

1. 키가 1인 사람의 왼쪽에 2명이 있으므로 answer에서 0을 두 번 건너뛰고 3번째 자리에 줄을 선다. 
   answer = [0, 0, 1, 0]
2. 키가 2인 사람의 왼쪽에 1명이 있으므로 answer에서 0을 한 번 건너 뛰고 2번째 자리에 줄을 선다. 
   answer = [0, 2, 1, 0]
3. 키가 3인 사람의 왼쪽에 1명이 있으므로 answer에서 0을 한 번 건너뛰고, 이미 줄을 선 2와 1을 건너 뛰고 4번째 자리에 줄을 선다. 
   answer = [0, 2, 1, 3]
4. 키가 4인 사람의 왼쪽에 0명이 있으므로 맨 앞에 줄을 선다. 
   answer = [4, 2, 1, 3]

 

 

 

소스코드

 

//1138번: 한 줄로 서기
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N;
    cin >> N;
    vector<int> v(N), answer(N);
    for(int i = 0; i < N; i++)
        cin >> v[i];
    
    for(int i = 0; i < N; i++) {
        int j = 0;
        while(v[i] != 0) {  //줄을 선 순서 찾기
            if(answer[j] == 0) {
                v[i]--;
            }
            j++;
        }
        while(answer[j] != 0) j++;  //사람이 서있으면 다음으로 이동
        answer[j] = i + 1;
    }
    
    for(int i = 0; i < N; i++)
        cout << answer[i] << ' ';
 
    return 0;
}

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)