백준 1700번 멀티탭 스케줄링 문제 해설/코드 (파이썬)

코드만 궁금한 분은 링크

GitHub - Rhyankwon/algorithms

 

문제는 간단하다. N크기의 리스트가 있고 거기에 주어진 순서대로 숫자들을 넣으면 된다.

 

당연히, 이 때 이미 리스트 안에 있는 숫자는 순번을 pass하면 되고 그렇지 않은 경우는 안쪽의 수를 꺼내고 지금의 숫자를 리스트 안에 넣어야 한다.

 

문제에서 요구하는 답은, 이 때 리스트 안의 수를 제거하는 횟수의 최솟값이다.

 

이 때 최소한으로 리스트 안의 값을 제거하려면 다음과 같은 로직이 필요하다.

 

1. 이후에 다시 등장하지 않는 수를 제거하는게 최선

2. 가장 멀리 떨어진 수를 제거하는건 차선

 

따라서 값 삭제를 해야하는 상황이 올 때마다 이미 리스트 안에 있는 값들이 뒷쪽에 나오는지, 얼마나 멀리 뒤에 나오는지 확인하는 과정이 필요하다.

 

위의 로직을 생각하면 구현은 어렵지 않은 문제이다.