[Baekjoon 2002 / Python / 실버1] 추월

문제

 

구현, 문자열, 해시 테이블 문제이다.

 

# 실버1 -> 구현, 자료구조, 문자열, 해시

# 들어간 순서 해시 테이블로 저장해두기

# 나온 차량 순서 기준으로, 이후 나올 차량의 "들어올 때 인덱스"를 찾아서

# 나온 차량의 들어올 때 인덱스가 한 번이라도 더 클 경우 result += 1

N = int(input())

go_in = dict()

come_out = []

for i in range(N):

    go_in[input()] = i

for i in range(N):

    come_out.append(input())

result = 0

for i in range(len(go_in) - 1):

    # 현재 나온 차량의, 들어올 때 순서

    out_car = go_in[come_out[i]]

    # 이후 나올 차량의, 들어올 때 순서와 비교하여 추월일 경우 추가

    for j in range(i+1, len(go_in)):

        if out_car > go_in[come_out[j]]:

            result += 1

            break

print(result)

 

처음엔 각 차량의 입구/출구 에서의 절대적인 위치만을 비교하여, 기존 위치보다 빠른 인덱스에 있다면 추월한 것으로 생각하여 구현했지만 틀렸었다.

 

조금 더 생각해보니, 한번 추월을 한 후 다른 차량에게 여러번 추월당하면 추월 차량이면서도 추월하지 않은 것으로 판단될 수 있기 때문이었다. 그래서 상대적인 위치를 파악해야 했다.

 

나오는 차량을 순서대로 기준으로 잡아, "해당 차량의 들어올 때 위치"와 "해당 차량 이후로 나올 모든 차량들의 들어올 때 위치" 를 비교하여, 한 번이라도 "해당 차량의 들어올 때 위치"가 더 컸다면(인덱스가 더 크다면, 즉 뒤에 있었다면) 추월한 것으로 간주하고 결과에 추가해 주면 된다.

 

결과