[BOJ/C++/2002] 추월

👀 문제

 

[문제 요약]

- 대근: 차가 터널에 들어가는 순서대로

- 영식: 차가 터널에서 나오는 순서대로

=> 터널 내부에서 반드시 추워했을 차가 몇 대인지 출력

---

📝 접근 방법

차량 번호(string)와 들어간 순서(int)를 저장하기 위해 처음에는 vector<make_pair<string, int> > 를 사용할까 생각했지만

차량 번호를 빨리 탐색해서 순서를 확인하는 게 좋을 거 같아 map<string, int>를 사용하였다. 

 

일단 n개의 줄만큼 입구에서 들어간 차량의 순서를 저장한다.

ZG431SN -> 0
ZG5080K -> 1
ST123D    -> 2
ZG206A   -> 3

이런 식으로 차량 번호를 key로 해서 저장하는 map을 사용하였다.

 

그리고 그 다음 n개의 줄만큼은 출구에서 나오는 차량이 입장할 때는 몇 번째였는지 계산하고 그 값을 백터에 저장한다.

차량번호	퇴장 순서	입장 순서
ZG206A	0	3	v[0]
ZG431SN	1	0	v[1]
ZG5080K	2	1	v[2]
ST123D	3	2	v[3]

 

그리고 이제 추월한 차량의 개수를 확인해야 한다.

"추월을 한다" -> 먼저 들어간 차보다 내가 먼저 나오면 추월한 거

 

v[0] = 3 (ZG206A) -> 제일 마지막에 들어갔다.

- v[1] = 0 

- ZG206A는 제일 마지막에 들어갔는데 퇴장 순서가 제일 빨랏으므로 반드시 추월

 

v[1] = 0 (ZG431SN)

- v[2] = 1 | 추월 X

- v[3] = 2 | 추월 X

 

v[2] = 1 (ZG5080K)

- v[3] = 2 | 추월 X

 

이거를 정리하면 

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (v[i] > v[j]) {
            cnt++;
            break;
        }
    }
}

이런 식으로 추월한 차량의 개수를 계산할 수 있다.

 

 

---

😎 해결 코드

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

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

    int n; cin >> n;        // 차량의 수
    string s;

    map<string, int> m;
    vector<int> v(n);

    for (int i = 0; i < n; i++) {
        cin >> s;
        m[s] = i;       // 들어온 순서대로 기록
    }

    for (int i = 0; i < n; i++) {
        cin >> s;
        v[i] = m[s];    // 나오는 차량을 들어온 번호대로 벡터에 저장
    }

    int cnt = 0;    // 추월한 차량의 개수

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (v[i] > v[j]) {
                cnt++;
                break;
            }
        }
    }

    cout << cnt;
}

---

⚠️ 틀리거나 시간이 오래 걸린 이유

---

📚 배운 점

map: key와 value 한 쌍으로 이루어진 자료형

- 각 노드가 key, value 쌍으로 이루어진 Tree 구조를 띄고 있음

- 일반 map은 key 값을 오름차 순으로 정렬하여 저장함. (속도가 중요하면 unordered_map을 사용하기도 함)