[백준, C++] 1138 - 한 줄로 서기

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

1138번: 한 줄로 서기

 

문제 분석

N명의 사람이 정해진 순서대로 줄을 선다. 그런데 각 사람들은 자신의 키보다 큰 사람이 왼쪽에 몇 명 있는지를 알고 있다(전체 순서는 따로 공개된 게 아니고). 그리고 각 사람들의 키는 1 ~ N 사이이고, 중복이 없다.

 

예시를 보자.

4명의 사람이 있고, 각 사람의 키는 1, 2, 3, 4이다. 이 때, 각 사람들이 알고 있는, 자신의 키보다 큰 왼쪽 사람의 수는 각각 아래와 같다.

2, 1, 1, 0

 

이 문제를 어떻게 풀 수 있을까 ? 하고 혼자 생각해봤는데, 머리로 계산하는 방법을 코드로 그대로 옮기면 되겠다고 생각했다.

 

키가 4인 사람은 자신보다 키가 큰 사람이 왼쪽에 0명 있다. 사실 이 말은 당연하다. 키가 4인 사람은 어디에 서 있어도 자신보다 키가 큰 사람이 없을 것이다. 그러므로, 키가 4인 사람을 아무데나 세워도 된다고 생각해보자.

 

[4]

 

다음으로 키가 3인 사람을 보자. 자신보다 키가 큰 사람이 왼쪽에 1명 있다고 한다. 이는 키가 3인 사람은 키가 4인 사람의 오른쪽에 서 있다는 말이 된다. 즉, 줄의 맨 앞의 1칸 뒤에 선다는 뜻이다.

 

[4, 3]

 

다음으로 키가 2인 사람을 보자. 자신보다 키가 큰 사람이 왼쪽에 1명 있다고 한다. 이는 키가 2인 사람은 키가 4인 사람과 키가 3인 사람의 사이에 서 있다는 말이 된다. 즉, 줄의 맨 앞의 1칸 뒤에 선다는 뜻이다.

 

[4, 2, 3]

 

마지막으로 키가 1인 사람을 보자. 자신보다 키가 큰 사람이 왼쪽에 2명 있다고 한다. 이는 키가 1인 사람은 키가 2인 사람과 키가 3인 사람의 사이에 서 있다는 말이 된다. 즉, 줄의 맨 앞의 2칸 뒤에 선다는 뜻이다.

 

[4, 2, 1, 3]

 

이를 어떻게 로직으로 풀어낼 수 있을까 ?

 

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> counts;
vector<int> result;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; i++) {
        int count;
        cin >> count;
        counts.push_back(count);
    }

    for (int i = counts.size() - 1; i >= 0; i--) {
        int number = i + 1;
        result.insert(result.begin() + counts[i], number);
    }

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << "\n";

    return 0;
}

 

코드 설명

사람들의 줄을 의미하는 result라는 빈 벡터를 선언해둔다.

 

1번 사람부터 N번 사람까지 있다고 했을 때, 우리는 N번 사람부터 1번 사람까지 역순으로 순회한다. 그러면서, 현재(i) 사람이 줄(result)에 들어갈 위치를 정해줄 것이다. 줄에 들어갈 위치는, 줄의 시작인 맨 앞에서부터 몇 번째 위치인지에 해당한다. 이는 입력으로 받은 counts[i]에 해당한다.

 

역순으로 순회한다는 개념이 여기서 매우 중요하다. 그 이유는, 역순으로 순회하기 때문에 줄에는 키가 큰 순서대로 사람들이 삽입된다는 '전제' 가 깔려 있기 때문이다. 즉, i번째 사람이 줄에 삽입될 때 그 사람은 줄에서 키가 가장 작은 사람이다. 어느 위치에 들어가든 말이다.

 

이를 활용한다면, i번째 사람보다 키가 큰 사람이 왼쪽에 m명 있다고 하면, i번째 사람을 줄에 넣을 때 앞에서부터 m번째에 집어넣으면 된다는 뜻이 된다.

 

이 개념을 활용해 문제를 풀 수 있었다.