피카츄처럼 살고싶어요.

생각해봅시다!

• 멀티탭이 꽉 찼는데 새로운 전기용품을 꽂으려면, 지금 꽂힌 전기용품 중 하나를 빼야 합니다.
• 이때 어떤 걸 빼야 할까요? 곧 다시 쓸 용품을 빼기보다는...
  • 1순위로 앞으로 다시 사용할 일이 없는 전기용품을,
  • 만약 모든 전기용품이 다시 사용된다면 2순위로 가장 나중에 사용할 전기용품을 빼는 것이 좋습니다.
• 그러므로 각 전기용품이 앞으로 언제 사용되는지 저장해 두어야 문제풀이가 쉬워집니다.
• 이 글에서는 집합, 딕셔너리와 데크(deque)를 활용해서 풀어보겠습니다.

입력

from collections import deque
import sys
input = sys.stdin.readline

# N: 멀티탭 구멍의 수, K: 전기용품의 총 사용횟수 

N, K = map(int, input().split())
# 전기용품의 사용 순서
tools = list(map(int, input().split()))

curr = set()   		# 현재 멀티탭에 꼽힌 전기용품들
count = 0      		# 정답: 멀티탭에서 전기용품을 뺀 욋수

• 현재 멀티탭에 꽂힌 전기용품은 집합 curr로 관리합니다.
  • x in curr로 특정 전기용품이 멀티탭에 꽂혀 있는지 확인하거나
  • curr.add(x)로 전기용품을 꽂고
  • curr.remove(x)로 전기용품을 빼는데
  • 시간복잡도가 $O(1)$밖에 소요되지 않아 효율적입니다.
• 전기용품의 사용 순서는 리스트 tools로 관리합니다.
  • e.g., 전기용품을 2 -> 3 -> 2 -> 3 -> 1 -> 2 -> 3 순으로 사용하는 경우
  • tools는 [2, 3, 2, 3, 1, 2, 3].
• 멀티탭에서 전기용품을 뺀 총 횟수, 즉 우리가 찾는 정답은 count 변수로 관리합니다.

딕셔너리와 데크

when_use = dict()  # 각 전기용품의 사용 시점을 저장할 딕셔너리
for i in range(K):
    if tools[i] not in when_use:
        when_use[tools[i]] = deque()
    when_use[tools[i]].append(i)

• 딕셔너리 when_use를 이용해 각 전기용품이 사용되는 시점을 기록합니다. (지금 보니 굉장히 직설적인 이름이다...)
• 이때 키는 전기용품의 번호, 값은 해당 전기용품이 사용되는 시점들을 저장한 데크(deque)입니다.
• 리스트 tools의 각 원소를 순회하며, 각 전기용품의 사용시점을 when_use에 추가합니다.
  • 이때 tools[i] (키) 는 i (값) 번째 시점에 사용되는 전기용품 번호입니다.
  • 즉 when_use[tools[i]]에 i를 대입하면 됩니다.
• e.g., tools가 [2, 3, 2, 3, 1, 2, 3]인 경우
  • when_use는 아래와 같이 구성됩니다.

{
	2: deque([0, 2, 5]), 
    3: deque([1, 3, 6]), 
    1: deque([4])
}

• 이후에는 각 전기용품이 이후에 언제 다시 사용될 예정인지 판단해야 합니다.
  • 따라서 용품을 사용할 때마다 데크 when_use[용품번호]에서 .popleft()로 현재 시점을 제거합니다.
  • 그리고 남은 데크의 맨 앞(when_use[전기용품][0])을 확인하면, 각 용품의 다음 사용 시점을 알 수 있습니다.
  • (데크가 비어 있으면, 더 이상 쓸 일이 없는 용품이란 뜻이죠.)
  • 오호! 그럼 나중에 이걸로 어떤 물건을 빼야 하는지 알 수 있겠군요!!
• 데크를 사용하는 이유: popleft()가 $O(1)$이라서 효율적입니다.

멀티탭을 뺀 횟수 계산

for i in range(K):
    # 플러그가 꽉 찼는데 새로운 앨 넣어야 해??
    # 그럼 하날 빼야즤~~~~ 하하호호~~~
    if len(curr) == N and tools[i] not in curr:
    
        # 뺄 용품의 번호를 찾아 out_tool에 저장
        # 현재 꽂힌 용품 중, 제일 늦게 사용하는 용품의 사용시점을 latest_time에 저장
        latest_time = -1 
        
        # 현재 꽂힌 용품 중 하나를 선택해야 한다
        for p in curr:
            # 1순위: 앞으로 쓸 일이 없는 용품 -> 바로 제거 확정.
            if not when_use[p]:
                out_tool = p
                break
        
            # 2순위: 앞으로 사용할 시점이 제일 늦은 용품 -> 일단 최댓값 갱신하고 킵해두기.
            elif when_use[p][0] > latest_time:
                out_tool = p
                latest_time = when_use[p][0]
                
        # 선택한 용품 제거, 교체횟수 증가
        curr.remove(out_tool)
        count += 1
    
    curr.add(tools[i]) 				# 용품을 멀티탭에 꼽기
    when_use[tools[i]].popleft() 	# when_use 딕셔너리에서 현재 시점 제거

• for i in range(K)로, 순서대로 사용할 전기용품 (tools[i]))을 확인합니다.
  • curr.add(tools[i])로 플러그에 꽂아 줍니다.
  • curr은 집합이라 중복 원소를 허용하지 않기 때문에, 이미 꽂혀 있으면 (tools[i]가 curr에 이미 존재하면) 아무것도 추가되지 않습니다.
  • 이후 when_use[tools[i]].popleft()를 해 줍니다.

• 단, 플러그가 꽉 차 있고 (len(curr) == N), 지금 사용할 전기용품이 꽂혀 있지 않은 경우 (tools[i] not in curr)
  • 기존 용품 중 하나를 무조건 빼 줘야 합니다.
  • 앞서 언급했듯이 1순위로 앞으로 다시 사용할 일이 없는 전기용품을, 모든 전기용품이 이후에도 사용된다면 2순위로 가장 나중에 사용할 전기용품을 빼야 합니다.
• 현재 꽂힌 전기용품들을 하나씩 확인하며, 각 용품의 남은 사용 시점을 확인합니다 (when_use[p])
  • when_use[p]가 비어 있으면, 해당 용품은 더 이상 사용되지 않으므로, 바로 제거 대상이 됩니다. (1순위)
  • 그렇지 않으면, 가장 앞의 값 when_use[p][0]가 그 용품의 다음 사용 시점입니다. 이 값을 기준으로, 가장 늦게 다시 사용되는 전기용품을 골라 jail_mun_tool에 저장합니다. (2순위)
• 뺄 전기용품 jail_mun_tool을 curr.remove()로 멀티탭에서 제거하고, 교체 횟수인 count도 1 추가해 줍니다.
• 이후엔 앞서 한 것처럼 새로운 물건을 꽂으면 됩니다.

풀이

from collections import deque
import sys
input = sys.stdin.readline

# N: 멀티탭 구멍의 수, K: 전기용품의 사용횟수 
N, K = map(int, input().split())
# 전기용품의 사용 순서
tools = list(map(int, input().split()))

curr = set()   # 현재 멀티탭에 꼽힌 전기용품을 저장
count = 0      # 정답: 멀티탭을 넣고 뺀 횟수

when_use = dict()  # 각 전기용품의 사용 시점을 저장
for i in range(K):
    if tools[i] not in when_use:
        when_use[tools[i]] = deque()
    when_use[tools[i]].append(i)

for i in range(K):
    # 플러그가 꽉 찼는데 새로운 앨 넣어야 해??
    # 그럼 하날 빼야즤~~~~ 하하호호~~~
    if len(curr) == N and tools[i] not in curr:
    
        # 뺄 용품의 번호를 찾아 out_tool에 저장
        # 현재 꽂힌 용품 중, 제일 늦게 사용하는 용품의 사용시점을 latest_time에 저장
        latest_time = -1 
        
        # 현재 꽂힌 용품 중 하나를 선택해야 한다
        for p in curr:
            # 1순위: 앞으로 쓸 일이 없는 용품 -> 바로 제거 확정.
            if not when_use[p]:
                out_tool = p
                break
        
            # 2순위: 앞으로 사용할 시점이 제일 늦은 용품 -> 일단 최댓값 갱신하고 킵해두기.
            elif when_use[p][0] > latest_time:
                out_tool = p
                latest_time = when_use[p][0]
                
        # 선택한 용품 제거, 교체횟수 증가
        curr.remove(out_tool)
        count += 1
        
    curr.add(tools[i]) 				# 용품을 멀티탭에 꼽기
    when_use[tools[i]].popleft() 	# when_use 딕셔너리에서 현재 시점 제거

print(count)

• 이 모든 과정을 거치고 count를 출력하면 됩니다.

시간 복잡도

• 총 용품의 사용 횟수가 $K$번, 플러그에 꽂을 수 있는 최대 용품 수가 $N$개일 때
• 각 전기용품의 사용 시점을 when_use에 저장할 때 $O(K)$
• 총 $K$개의 전기용품을 사용 (for i in range(K))
  • 이때 전기용품을 빼야 하는 경우, 플러그의 $N$개 물품 중 하나를 찾아서 제거해야 함. 최악의 경우 $N$개를 모두 확인해야 하므로 $O(N)$
  • 최종적으로 $O(N \times K)$
• 전체 $O(N \times K)$. $N \leq 100, K \leq 100$이니 시간초과 날 리 없음.

기억할 점

• 이중 반복문을 두려워하지 말자! 문제의 크기가 작으면 해볼 법하다.