[백준] 2002 추월

백준 2002 추월

문제

대한민국을 비록한 대부분의 나라에서는 터널 내 차선 변경을 금지한다.

소문난 명콤비 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다.

대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널을 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량의 번호의 목록을 보고, 터널 내부에서

반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다.

대근이와 영식이를 도와 이를 구하는 프로그램을 작성해보자.

입력

• 첫 줄: 차의 대수
• 두 번째 줄 ~ N+1 번째 줄: 대근이가 적은 차량의 번호
• N+2 ~ 2N+1: 영식이가 적은 차량의 번호 목록
• 차량의 번호는 영어 대문자와 숫자로 이루어짐

출력

추월 했을 것으로 여겨지는 차가 몇 대인지 출력

문제 해결 방식

1. 입장한 차와 나온 차를 따로 입력받는다. (입장한 차 리스트=A, 나온 차 리스트 = B)
2. 마지막에 입장한 차(a)와 마지막에 나온 차(b)를 비교한다.
3. a와 b의 차 번호가 같지 않다면 마지막 입장한 차가 추월했다는 의미이므로 count 증가
4. B에 위치한 a를 A에서의 위치와 일치하도록 변경한다. (맨 뒤로 오도록 변경)

5. 마지막 이전의 차번호들 비교를 반복 (A와 B가 같아질 때까지)

   코드

    carNum = int(input())
    entranceList = [input() for _ in range(carNum)]
    exitList = [input() for _ in range(carNum)]
    count = 0
    target = carNum - 1
   
    while entranceList != exitList:
        if entranceList[target] != exitList[target]:
            car = entranceList[target]
            exitList.remove(car)
            exitList.insert(target, car)
            count += 1
        target -= 1
           
    print(count)
   

오답

1. 입장한 차의 번호와 같은 번호를 나온 차의 리스트에서 찾는다.
2. 입장한 차 리스트에서의 위치와 나온 차의 리스트에서의 위치를 비교한다.
3. 나온 차 리스트에서의 위치 > 입장한 차 리스트에서의 위치인 경우 count 증가

• 반례: 이 경우 예를 들어 입장한 차 순서가 a b c d 이고 나온 순서가 d a c b인 경우 실제 추월한 차는 2대이지만, 1을 출력한다.
  

  오답 코드

    carNum = int(input())
    entranceList = [input() for _ in range(carNum)]
    exitList = [input() for _ in range(carNum)]
    count = 0
  
    for i in range(carNum):
        position = 0
        for j in range(carNum):
            if exitList[j] == entranceList[i]:
                position = j
                break
        if position < i:
            count += 1
  
    print(count)