[백준-Python] 추월 : 2002번

🥈 Silver1

 

https://www.acmicpc.net/problem/2002

 

 

❎ 1차 풀이

# enter, exit 각각의 순위 dict 생성
# 순위 변동 비교

import sys

input=sys.stdin.readline
n=int(input())


#enter 
enter_dic={}
for i in range(1,n+1):
    enter_dic[input().rstrip()]=i
enter_dic=dict(sorted(enter_dic.items()))


#exit
exit_dict={}
for i in range(1,n+1):
    exit_dict[input().rstrip()]=i
exit_dict=dict(sorted(exit_dict.items()))

#순위변동 비교
rank=[]
for i in range(n):
    enter_rank=list(enter_dic.values())[i]
    exit_rank=list(exit_dict.values())[i]
    rank.append(exit_rank-enter_rank)


print(len(list(filter(lambda x:x<0,rank))))

 

감이 안잡혀서 일단 테스트케이스를 보면서 다음과 같은 방식으로 들어온 순위와 나간 순위를 빼서 음수 즉, 나간순서가 들어온 순서보다 뒤쳐졌을때 추월로 생각을 해보았다.

역시 오답이였다!

 

이건 상대를 고려하지 않은 자신의 순위 변동만을 고려한 방식이였다. 

 

 

출구에서 나오는 순서가 들어온 순서보다 작으면 추월

# 출구에서 나오는 순서가 들어온 순서보다 작으면 추월
for i in range(n):
    name = list(out_dict.keys())[i]
    if out_dict[name] < in_dict[name]:
        result += 1

👉🏻 이 방식 또한, 자신의 순서만을 비교하는것이기 때문에 상대적인 위치변화를 놓칠 수 있다.

 

✅ 정답 풀이

import sys
input=sys.stdin.readline
n=int(input())

in_dict={}
out_dict={}

#입구 순서 dict 생성
for i in range(n):
    in_dict[input().rstrip()]=i

#출구 순서 dict 생성
for i in range(n):
    out_dict[input().rstrip()]=i


result=0
out_keys=list(out_dict.keys())
#출구에서 나오는 순서가 들어온순서보다 작으면👉🏻 추월
for i in range(n-1):
    name=out_keys[i] #나온 차량
    for j in range(i+1,n):
        #비교할 차량
        next_in=in_dict[out_keys[j]]
        if in_dict[name]>next_in:
            result+=1
            break
        
    
print(result)

메모리	시간
31120KB	76ms

 

 

💡 지금 나온 차의 들어간 순서보다 나중에 온 차들의 들어간 순서가 앞인 경우에 추월

 

👉🏻 순회를 돌면서 i+1이후부터 n까지 순회를 하면서, 들어온 순서를 비교해, 현재 나온 차량의 순서보다 앞서 들어온차가 발견되면 추월이라고 카운트를 해주고, for문을 빠져나온다.