[백준] 2002 - 추월

1. 문제

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

2002번: 추월

 

2. 접근

1. 데이터를 받아올 때 인덱스 값을 통해서 그 값을 통해 출구를 나갈때 차들의 순서를 확인하려고 한다

2. 입구와 출구를 left, right로 나눠서 보자

3. LIS를 로직으로 출구에서 나오는 차들의 idx를 파악해보자 그러면 답이 나온다

 

또 다른 방법은 

-> 1~n까지는 dict 에 넣고 n+1 ~2*n까지는 stack에 넣어서 판단을 해볼 수 있다.

 

3. 풀이

# 2002 실버1
import sys
input = sys.stdin.readline

n = int(input())

terminal = []
for i in range(1,(2*n)+1):
    car = input().rstrip()
    if i <= n:
        terminal.append([car, i])
    else:
        for j in range(len(terminal)):
            if car == terminal[j][0]:
                terminal.append([car, terminal[j][1]])

left = terminal[:n]
right = terminal[n:]
# print(left)
# print(right)

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if right[i][1] > right[j][1]:
            cnt += 1
            break
print(cnt)

 

또 다른 방법

N = int(input())
answer = 0
enter, out = dict(), []
for i in range(N):
	car = input()
	enter[car] = i
for _ in range(N):
	car = input()
	out.append(car)
 
for i in range(N-1):
	for j in range(i+1, N):
		if enter[out[i]] > enter[out[j]]:
			answer += 1
			break
print(answer)