3-5. BOJ 1138번 - 한 줄로 서기

다나·2023년 3월 12일

코딩테스트 스터디

목록 보기

30/32

1. 관련 문제 🎯

문제 : 백준 1138 한 줄로 서기 👥
난이도 : 실버 2

2. 문제 소개 🧩

1️⃣ N명의 사람들은 매일 아침 한 줄로 선다.

2️⃣ 이때, 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다.

키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다.

3️⃣ N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

4️⃣ 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력한다.

3. 문제 풀이 🖌️

아래의 예시를 통해서 문제를 풀어보자!!
다음의 예시를 다음과 같은 파란색의 표로 나타낼 수 있다.
이때, 사람의 키는 고유하기 때문에 문제를 풀때는 사람의 키로 해당 사람을 나타낼 것이다~!
만약 사람의 키가 1인 사람을 예시로 들어보면, 자신보다 큰 사람이 왼쪽에 2명이 있어야 하므로 ⏹️⏹️ 1로 생각할 수 있다. (ex. 231, 321 ...)

☝️ 이때 고민하다가, 앞에서부터 고려하는 것이 아닌 마지막부터 고려해야겠다는 생각이 들었다!

그 이유는 뒤에서부터 고려하면 자동적으로 키가 큰 순서대로 비교할 수 있기 때문이다!

마지막 키부터 어디에 위치할지를 정한다.
그 다음 키는 왼쪽 사람의 수가 얼마있는지에 따라서 위치가 정해진다.

1️⃣ 키가 4인 사람(N번째 사람) : 가장 크기 때문에 자신보다 큰 사람이 없어서 왼쪽 사람의 수는 0이 될 수 밖에 없다.
2️⃣ 키가 3인 사람 : 왼쪽 사람의 수가 1이므로 자신보다 큰 사람은 4밖에 없어서 4의 바로 뒤에 위치하게 된다.
3️⃣ 키가 2인 사람 : 왼쪽 사람의 수가 1이므로 자신보다 큰 사람이 1명이어야 하므로 4와 3 사이에 위치하게 된다.
4️⃣ 키가 1인 사람 : 왼쪽 사람의 수가 2이므로 4,2와 3 사이에 들어가게 된다.

✨ 즉, 해당 키를 삽입할 위치는 이미 구해진 배열에서 왼쪽 사람의 수번째에 들어간다!!

그 이유는 이미 구해진 배열에는 자신보다 큰 키를 가진 사람들뿐이기 때문이다.
그리고, 나중에 키가 삽입되더라도 자신보다 작은 키를 가진 사람들이 삽입되기 때문에 자신의 왼쪽 사람의 수에 영향을 주지 않는다!

4. 전체 코드 🔑

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

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

    int N = 0;
    int people[11];
    vector<int> lines;
    cin>>N;

    for(int i=1; i<=N; i++){
        cin>>people[i];
    }
    
    lines.push_back(N);
    for(int i=N-1; i>=1; i--){
        lines.insert(lines.begin()+people[i], i);
    }

    for(int ans : lines){
        cout<<ans<<" ";
    }
}