import sys
input = sys.stdin.readline
N,K = map(int,input().split())
seq = [*map(int,input().split())]
inuse = set()
cnt = 0
for i in range(K):
if len(inuse) == N and seq[i] not in inuse:
willuse = set()
for j in range(i+1,K):
if seq[j] in inuse:
Pop = seq[j]
willuse.add(seq[j])
if len(willuse) == N:
break
if len(willuse) == N:
inuse.remove(Pop)
else:
for Pop in inuse-willuse:
inuse.remove(Pop)
break
cnt += 1
inuse.add(seq[i])
print(cnt)
아이디어를 떠올리기는 쉬웠는데, 그게 맞는지를 판단하기가 어려운 문제였다.
내가 푼 알고리즘은 이러하다.
1. 사용할 물건을 inuse set에 넣는다.
2. 만약 set의 길이가 N보다 크고, 다음에 들어올 물건이 inuse 안에 없다면 3~6번
3. 앞으로 사용할 물건 중 inuse에 있는 물건을 willuse set에 N개까지 담는다. (inuse가 N개이므로)
4. 만약 willuse의 길이가 정확히 N이라면 가장 마지막에 담은 물건을 제거
5. 만약 willuse 길이가 N보다 작다면 willuse에 속해있지 않은 물건 중 아무거나 하나 제거
6. 제거할때마다 cnt +1
7. 결과 출력
여담) 몰랐는데 내 풀이가 파이썬 기준 성능 1위였다. 어쩐지 자꾸 풀이 읽었다고 알림이 뜨더라...