[baekjoon] 2002. 추월

✅ 문제

 

 

예제 입력을 보면서 이해를 해보자.

첫 줄에는 터널로 진입할 차량의 수 n, 터널에 들어간 순서대로 차량 번호 n개,  터널에서 나온 순서대로 차량 번호 n개

따라서 ZG206A 말고는 들어간 순서대로 나왔으니 이 차만 추월해서 답은 1이다.

 

---

✅ 풀이

💡 Point
1. 들어가는 순서대로 딕셔너리에 담음(key = 차번호, value=들어간 순서)
2. 나오는 순서대로 리스트에 담음
3. 추월 조회
  1) 나온 순서대로
  2) 그 차가 몇 번째 들어갔었는지, 그 다음 차가 몇 번째 들어갔었는지 비교하여
  3) 들어갈때보다 나온 순서가 크면 추월한 것으로 count 올린 후 다음 차 조회

n = int(input())
input_list = {}
output_list = []

# 입구에서 들어가는 순서로 딕셔너리를 만듦
for i in range(n):
    car_number = str(input()).strip()
    input_list[car_number] = i

# 출구에서 나오는 순서대로 리스트에 저장
for i in range(n):
    output_list.append(str(input()).strip())

# 추월한 차량 수
count = 0
# 나온 순서대로 하나씩 그 다음에 나온 차보다 먼저 나왔는지 비교
# 2개씩 비교하니까 n-1번 돌기
for i in range(n-1):
    for j in range(i+1, n): #현재 비교 차량 다음 차량부터
        if input_list[output_list[i]] > input_list[output_list[j]]:
            count += 1
            break
print(count)

 

이 코드는 마지막에 비교하는 데서 엄청 오래걸렸다. 딕셔너리의 key-value 쌍을 이용해 풀 수 있는 문제!