[그리디] 백준 1700. 플러그

플러그 자리 없으면 뽑는 건데, 젤 적게 뽑을 때의 횟수 구해라

 

포인트는, 

1. 플러그 검사해서, 꽉차면 하나 뽑고 시작해 (* 대신에 맨마지막에서는 안뽑아야함)

2. 플러그 꽂을 때는, 이미 꽂혀있는 건지 검사

3. 플러그 뽑을 때, 더 나중에 꽂아야 하는 애를 뽑아야함. (어려움, index 크기 비교로 풀었음)

 

n, k = map(int, input().split())
lst = list(map(int, input().split()))

plug = []

cnt = 0
for idx in range(k):
    i = lst[idx]
    later = -1
    res = lst[idx+1:]
    id = 0
    if i in plug:
        continue

    while len(plug) == n and id < n and idx != k:
        p = plug[id]
        if p not in res:
            plug.remove(p)
            cnt += 1
            continue

        else:
            later = max(later, res.index(p))
        id += 1

    if later != -1 and idx < k and len(plug) == n:
        plug.remove(res[later])
        cnt += 1

    if i not in plug and len(plug) < n:
        plug.append(i)
        continue

print(cnt)

 

 

그래도 내 힘으로 짰다. 뿌-듯 

골드 1 희희희힇