백준 2002번 [추월](C++) -yes6686- 티스토리

백준 문제 풀이: 2002 (추월)

---

문제 링크: https://www.acmicpc.net/problem/2002

문제 설명:

차량들이 터널에 진입한 순서와 터널에서 나온 순서가 주어집니다. 추월한 차량의 수를 계산하는 문제입니다. 차량이 추월했다는 것은, 터널에 진입한 차량 중 뒤에서 들어온 차량이 앞서서 나왔음을 의미합니다.

---

문제 해결 코드

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

int arr[1001]; // 차량의 터널 진입 순서를 저장
map<string, int> mp; // 차량 이름과 진입 순서 매핑

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

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

    // 터널 진입 순서 저장
    for (int i = 0; i < n; i++) {
        cin >> s;
        mp[s] = i;
    }

    // 터널에서 나온 순서를 배열로 저장
    for (int i = 0; i < n; i++) {
        cin >> s;
        arr[i] = mp[s];
    }

    // 추월 차량 계산
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) { // 터널 진입 순서보다 앞서 나온 경우
                ans++;
                break;
            }
        }
    }

    cout << ans << '\n'; // 추월한 차량의 수 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 차량의 터널 진입 순서를 저장하고, 터널에서 나온 순서와 비교하여 추월 여부를 판별합니다.
• 구현 세부사항:
  • map<string, int> mp: 차량 이름과 터널 진입 순서를 매핑하여 빠르게 순서를 참조할 수 있습니다.
  • arr[i]: 터널에서 나온 차량의 진입 순서를 저장하여 정렬 상태를 비교합니다.
  • 이중 루프를 사용해 차량이 추월했는지 판별합니다.
• 시간 복잡도 분석:
  • 터널 진입 순서를 저장하는 데 O(n)입니다.
  • 추월 여부를 확인하는 이중 루프는 O(n²)입니다.
  • 전체 시간 복잡도는 O(n²)입니다.
  문제의 n(차량 수)이 최대 1,000이므로 O(n²) 풀이가 가능하지만, 개선 여지가 있습니다.

---

결과

차량의 터널 진입 및 출력 순서를 기준으로 추월한 차량의 수를 정확히 계산합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!