[BOJ] 2002. 추월 (Python/구현/Silver 2)

 

---

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

---

풀이

1️⃣ 차량 진입 순서 기록

차량이 진입할 때의 순서를 딕셔너리로 저장하여, 각 차량의 진입 위치를 빠르게 조회할 수 있게 한다.

car_in_dict = dict(zip(car_in, range(1, len(car_in) + 1)))

 

 

2️⃣ 차량 진입 순서 인덱스 변환

차량이 나가는 순서에 따라 각 차량의 진입 순서 인덱스를 리스트로 변환한다. 이 리스트는 나가는 순서를 진입 순서로 매핑한 형태이다.

for i in car_out:
    calc.append(car_in_dict[i])

 

 

3️⃣ 추월 여부 확인

calc 리스트를 순차적으로 확인하여, 앞선 차량의 진입 순서가 뒤 차량보다 크다면 추월이 발생한 것으로 간주하고 추월 횟수(result)를 증가시킨다.

for i in range(len(calc) - 1):
    for j in range(i + 1, len(calc)):
        if calc[i] > calc[j]:  # 뒤에 있어야 할 차량이 앞에 나오면 추월 발생
            result += 1
            break

 

 

4️⃣ 결과 출력

최종 추월 횟수를 출력한다.

 

 

Solution

n = int(input()) #차량 수
car_in = [input().strip() for _ in range(n)]  # 들어가는 순서
car_out = [input().strip() for _ in range(n)]  # 나가는 순서

result = 0
car_in_dict = dict(zip(car_in, range(1, len(car_in) + 1)))  # 딕셔너리 생성
calc = []
for i in car_out:
    calc.append(car_in_dict[i])  # 나가는 차량 인덱스 저장

# 출구 순서에서 추월 여부 확인
for i in range(len(calc) - 1):
    for j in range(i + 1, len(calc)):
        if calc[i] > calc[j]:  # 뒤에 있어야 할 차량이 앞에 나오면 추월 발생
            result += 1
            break

# 최종 추월 횟수 출력
print(result)

 

 

set를 사용한 풀이

n = int(input())
car_in = [input().strip() for _ in range(n)]  # 들어가는 순서
car_out = [input().strip() for _ in range(n)]  # 나가는 순서

# 각 차량이 들어온 순서를 저장
car_in_dict = {car: idx for idx, car in enumerate(car_in)}

# 차량 출구에서 추월을 확인
result = 0
passed_cars = set()  # 이미 나간 차량을 기록

for car in car_out:
    car_in_index = car_in_dict[car]
    
    # 이미 나간 차량의 인덱스가 현재 차량보다 크면 추월 발생
    if any(car_in_dict[other] < car_in_index for other in passed_cars):
        result += 1
    
    # 나간 차량 기록
    passed_cars.add(car)

print(result)

 

• enumerate
  • enumerate는 반복 가능한 객체(리스트, 튜플 등)의 각 요소와 그에 해당하는 인덱스를 동시에 반환한다.
  • 예를 들어, car_in_dict = {car: idx for idx, car in enumerate(car_in)} 구문은 car_in 리스트의 각 차량 이름을 키로, 해당 차량이 리스트에서 등장한 인덱스 idx를 값으로 갖는 딕셔너리 car_in_dict를 만든다.
  • 이 경우 car_in_dict에는 차량의 이름과 해당 차량이 들어온 순서가 매핑된다.
• set
  • set은 중복 없는 순서 없는 데이터의 모음으로, 효율적으로 요소의 추가와 존재 여부를 확인할 수 있는 자료구조이다.
  • passed_cars = set()은 이미 나간 차량들을 저장하는 집합.
  • passed_cars.add(car) 구문을 통해 차량이 나가면서 그 차량이 passed_cars에 추가.
  • 이렇게 set을 사용하면 특정 차량이 이미 나갔는지 여부를 빠르게 확인할 수 있다.
• any
  • any는 주어진 반복 가능한 객체의 요소 중 하나라도 True일 경우 True를 반환, 모두 False면 False를 반환한다.
  • 이 코드의 if any(car_in_dict[other] < car_in_index for other in passed_cars) 부분은 passed_cars에 있는 차량 중 진입 순서가 현재 차량보다 먼저인 것이 하나라도 있는지 확인한다. 이는 현재 차량보다 먼저 나가야 할 차량이 이미 나갔는지 확인하기 위한 것이다.
  • 만약 조건을 만족하는 차량이 있으면 추월이 발생한 것으로 간주하여 result를 증가시킨다.

 

 

👩‍💻 회고

추월 문제.. 너무 어려웠다. 딕셔너리 생성 후 나가는 차량들을 매핑까지 했지만 그 이후가 문제였다. 뒤 인덱스부터 for 문을 돌려 뒤 인덱스 값보다 현재 인덱스 값이 더 크면 뒤 인덱스 값을 따로 저장하여 현재 위치와 계속 비교하려 했는데 이 과정이 잘 되지 않았다. 머리가 굳어버린 느낌이었다. 후..

---