2002. 추월

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 보러 가기

접근 과정

추월?

추월(追越) : 뒤에서 따라잡아서 앞의 것보다 먼저 나아감.
출처: 네이버 사전 https://ko.dict.naver.com/#/entry/koko/67abd764c52140038d9df17c76b60058

• 추월한다는 것은, 뒤에서 따라잡아서 앞의 것보다 더 나아간다는 것
• 그렇다면, 언제 추월한 것이라고 판단할 수 있을까?
  • 입장했을 때 순서보다 퇴장했을 때의 순서가 더 빠른 경우
  • 입장과 퇴장 순서가 동일하더라도, 먼저 입장했던 차를 퇴장했을 때 앞지른 경우
    
    
• 추월 차량을 파악하는 과정을 이렇게 정리할 수 있다!
  • 입장시의 순서를 번호판-순서 의 형태로 딕셔너리에 저장한다.
  • 퇴장한 순서 리스트의 요소들을 순회하며, 추월 차량의 수를 찾는다.
    • 퇴장 순서가 입장 순서보다 빠른 경우
    • 그 외에는, 퇴장 순서 리스트에서의 차량 A가 퇴장한 이후에 퇴장한 차량들 을 리스트로 뽑아내서 순회하며 차량 A가 입장하기 이전에 먼저 입장했던 차량들 을 담고 있는 리스트 안에 포함되어 있는지를 확인

첫 풀이

import sys

input = sys.stdin.readline
N = int(input())
order = dict()
cnt = 0

in_order = [input() for _ in range(N)]
for idx, car in enumerate(in_order):
    order[car] = idx

out_order = [input() for _ in range(N + 1, (N * 2) + 1)]
out_car = []

for idx, car in enumerate(out_order):
    if idx < order[car]:
        out_car.append(car)
        cnt += 1
    else:
        before_in_order = in_order[:order[car]]
        after_out_order = out_order[idx:]
        for remain_car in after_out_order:
            if remain_car != car and remain_car in before_in_order:
                out_car.append(car)
                cnt += 1
                break

print(cnt)

통과!..했지만 너무 시간이 오래 걸렸다. 분명 이보다는 더 빠른 풀이 방법이 있을 것이라고 생각했고, 개선 방안을 고민하게 되었다.

개선

추월 차량을 파악하는 과정 중 퇴장 순서가 입장 순서보다 빠르지 않은 경우의 코드에서 오랜 시간이 걸렸다. 여기에서 다시 반복문이 들어오면서, 결과적으로 O(N^2) 혹은 그 이상의 복잡도가 소요되어 시간이 오래 걸린 것 같다.

추월에 대한 모든 경우를 고려하면서, O(N) 정도의 시간복잡도로 문제를 해결할 수 있는 방법에 대해 고민했지만, 마땅한 방법이 떠오르지 않아 결국 다른 풀이를 참고하였다.
참고한 풀이 링크

다른 풀이들도 많았지만, 이 풀이가 가장 간결하면서 읽기 쉬웠던 것 같다.
N까지의 정수 인덱스 i에 대해서, 입장 - 퇴장 리스트의 i번째 값(차량)이 일치하지 않는 경우, 퇴장 리스트에서의 i번째 차량을 찾아 입장 리스트에서 해당 차량을 삭제했다가, 입장 리스트의 i번째 위치에 해당 차량을 다시 삽입한다.

처음 문제를 풀이할 때 생각했던 추월 차량의 조건 2가지를 위의 로직을 통해 간단하게 구현할 수 있었다..!

정리하면?

• 입장, 퇴장한 차량의 목록을 각각의 리스트로 담는다.
• 입력받은 정수 N의 범위만큼 순회
  • 입장 / 퇴장 차량 리스트에서 인덱스 i에 해당되는 차량이 동일한지 확인
  • 동일하지 않다면
    • 입장 차량 리스트에서 퇴장 차량 리스트의 i번째 요소를 삭제
    • 그 후, 입장 차량 리스트의 i번째 위치에 삭제한 차량을 삽입
    • 추월 차량의 수를 참조하는 변수에 1을 더한 값을 재할당

개선된 풀이

import sys

input = sys.stdin.readline
N = int(input())
cnt = 0

in_car = [input() for _ in range(N)]
out_car = [input() for _ in range(N)]

for i in range(N):
    if in_car[i] != out_car[i]:
        in_car.remove(out_car[i])
        in_car.insert(i, out_car[i])
        cnt += 1

print(cnt)

통과!

읽어주셔서 감사합니다!