[Baekjoon] 추월(BOJ 2002)

👀 문제 설명

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

 

입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자('A'~'Z')와 숫자('0'~'9')로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

 

출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

 

예제 입력 1

4

ZG431SN

ZG5080K

ST123D

ZG206A

ZG206A

ZG431SN

ZG5080K

ST123D

 

예제 출력 1

1

 

✍🏻풀이

처음에는 대근이가 입력한 차의 순서와 영식이가 입력한 차의 순서를 비교해 순서가 다른 차가 몇 대인지 구하면 된다고 생각해 정렬을 사용하려 했다.

영식이가 입력한 차를 대근이가 입력한 차의 순서대로 정렬해 순서가 바뀐 차가 몇 대인지 세려고 했으나, 정렬 기준이 명확하지 않아 실패했다..ㅠ

 

새로운 방식은 대근이가 입력한 차와 영식이가 입력한 차들을 모두 하나씩 비교하는 방식이다.

하나씩 비교해서 추월한 차량을 발견하면 추월한 차량 목록을 가지는 overtakeCars 벡터에 넣어준다.

비교가 끝났다면 overtakeCars 벡터의 size가 정답이 될 것이다!

 

필요한 변수

int N : 차의 대수 

vector<string> daegeun : 대근이가 적은 차량 목록 (터널에 들어갈 때)

vector<string> yeongsik : 영식이가 적은 차량 목록 (터널에서 나올 때)

vector<string> overtakeCars : 추월한 차량 목록

 

알고리즘

1. daegeun 벡터와 yeongsik 벡터를 하나하나 비교한다. (각 벡터의 index 0부터 하나씩 비교)

   1-1. 차량의 순서가 같으면 각 벡터의 index를 모두 1 증가시킨다.

   1-2. 차량의 순서가 다르면

          1-2-1. daegeun 벡터의 현재 위치의 차가 overtakeCars 벡터에 들어있는 차인지 확인한다.

                    1. 들어있다면, daegeun 벡터의 index를 1 증가시킨다.

                    2. 들어있지 않다면, yeongsik 벡터의 현재 위치의 차를 overtakeCars 벡터에 넣고 yeongsik 벡터의 index를 1 증가시킨다.

2. daegeun 벡터와 yeongsik 벡터를 모두 돌았다면 overtakeCars.size()를 반환해준다.

 

코드

//
//  BOJ_2002.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/07/19.
//  Copyright © 2020 조수민. All rights reserved.
//
//  추월(https://www.acmicpc.net/problem/2002)

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int N; // 차의 대수
vector<string> daegeun; // 대근이가 적은 차량 목록
vector<string> yeongsik; // 영식이가 적은 차량 목록
vector<string> overtakeCars; // 추월한 차량 목록

void input()
{
    // input
    cin >> N;
    daegeun.resize(N); // resizing vector
    yeongsik.resize(N); // resizing vector
    
    // input vector
    for (int i = 0; i < daegeun.size(); i++)
        cin >> daegeun[i];
    for (int i = 0; i < yeongsik.size(); i++)
        cin >> yeongsik[i];
}

bool isInOvertakeVector(string s, vector<string> &v)
{
    // 추월한 차량 목록에 있는 차인지 확인
    for (int i = 0; i < v.size(); i++)
        if (s == v[i])
            return true; // 목록에 있다면 true를
    
    return false; // 없다면 false를 반환한다.
}

int getOvertakesNumber()
{
    // daegeun 벡터와 yeongsik 벡터를 0부터 접근, 비교한다.
    int daegeunIndex = 0;
    int yeongsikIndex = 0;
    
    while (daegeunIndex < daegeun.size() && yeongsikIndex < yeongsik.size())
    {
        if (daegeun[daegeunIndex] == yeongsik[yeongsikIndex]) // 차량의 순서가 같으면 index를 1 증가시킨다.
        {
            daegeunIndex++;
            yeongsikIndex++;
        }
        else // 순서가 같지 않으면
        {
            if (isInOvertakeVector(daegeun[daegeunIndex], overtakeCars)) // daegeun 벡터의 daegeunIndex 위치에 있는 차가 overtakeCars에 들어있다면
                daegeunIndex++; // daegeunIndex를 1 증가시킨다.
            else // 아니라면
            {
                overtakeCars.push_back(yeongsik[yeongsikIndex]); // overtakeCars 벡터에 yeongsik 벡터의 yeongsikIndex 위치에 있는 차를 넣고
                yeongsikIndex++; // yeongsikIndex를 1 증가시킨다.
            }
        }
    }
    
    // daegeun 벡터와 yeongsik 벡터를 모두 돌았다면
    return (int)overtakeCars.size(); // overtakeCars 벡터의 size를 반환해주면 답이 된다.
}

int main()
{
    input();

    cout << getOvertakesNumber() << endl;
    
    return 0;
}