백준 2002 추월 파이썬

 

2002번: 추월

 

쏘 이지한 문제지만 풀이 방법이 마음에 들지 않아서 다른 분들 코드랑 비교해봤다. 

 

내가 푼 코드

deque 을 사용했다. 

문제에서 원하는 것은 추월한 차의 수를 구하는 것. 즉 first in first out 을 위배한 경우를 카운트 하는 것이다.

 

q1 이란 deque() 에 터널에 들어간 순서대로 원소를 담는다. 

그리고 차례대로 터널을 빠져나오는 원소(out) 가 q1 의 첫번째와 일치하지 않다면, 해당 원소는 추월한 것으로 간주할 수 있다.

추월한 차에 대한 카운트를 올려주고 deque 에서 해당 원소를 삭제해주자

from collections import deque

answer = 0
n = int(input())
q1 = deque()

for i in range(n*2):
    if i < n:
        q1.append(input())
    else:
        out = input()
        if out != q1[0]:
            q1.remove(out)
            answer += 1
        else:
            q1.popleft()

print(answer)

 

다 풀고 보니 q1.remove(out) 라인이 마음에 들지 않았다. 

 

🔗 참고한 코드

이 분은 for 문을 좀 많이 사용하셨지만, n 이 1000밖에 되지 않으므로 시간복잡도 문제로부터는 자유롭다. (이중 for 문 괜춘)

Exit 배열에 터널에 입장한 순서를 차례로 저장한다.

예를 들어 , a b c d e 순서로 입장했고, d c a b e 순서로 퇴장한다면 Exit 배열은 [3, 2, 0, 1, 4] 로 저장된다. (첫 순서는 0)

이 케이스에 추월 카운트는 2 가 된다 (d, c 가 추월맨)

즉 Exit 배열에서 자신보다 뒤에 위치한 원소의 값이 작다면, 해당 원소는 추월맨인 것이다.

아래 코드에선 이중 for 문을 사용해 자신보다 뒤에 위치한 원소 중 값이 작은 것의 개수를 카운트한다.

 

이중 for 문을 사용하지 않는 쪽으로 접근할 순 없는지 생각해봐야겠다.

N = int(input())
Entry = {input().rstrip() : i for i in range(N)}
Exit = list(int(Entry[input().rstrip()]) for _ in range(N))

res = 0
for i in range(N):
    for j in range(i, N):
        if Exit[i] > Exit[j]:
            res += 1
            break
print(res)