백준 1700번 멀티탭 스케줄링 (python) [G1]

그리디 알고리즘(Greedy Algorithm)

매 순간 최선의 선택으로 결과를 도출한다.
이 문제에서는 새로운 전자기기를 꽂을 때, 기존에 꽂혀있는 어떤 전자기기를 빼는가 가 가장 중요하다.

생각회로

• 멀티탭을 집합으로 구현한다.
• 처음 상황엔 멀티탭이 비어있으니, 순서대로 꽂는다.
• 처음부터 중복이 있을 수 있다. 그러므로 집합의 크기가 N이 될 때까지, K보다 작을 때까지 구한다.
• (중복 제거한 다음부터 반복문 진행) hubo 리스트 : index i 부터 마지막 input 까지의 요소, 꽂힐 후보들이다.
• 자리가 필요 없는경우 (이미 멀티탭에 꽂혀있다.) : continue
• 멀티탭 요소 중 후보에 없는 경우 : 뺀다.
• 그래도 자리가 없다 -> 후보를 뒤에서부터 살펴, 멀티탭에 있는 요소를 멀티탭에서 뺀다.
• 자리 생김 -> 꽂음 -> count++

주의사항

• i+1 번째 요소들을 후보에 넣는데, 처음부터 넣으면서 중복을 없애는 게 중요하다.
  [3, 1, 1, 2, 3, 3] is [3, 1, 2] not [1, 2, 3]
• python set 자료구조는 indexing이 되지 않는다. -> list로 복사해 해결
• 새로 꽂는 게 기준이므로, 마지막에 빈자리가 있어도 상관없다.

import sys

if __name__ == '__main__':
    N, K = map(int,sys.stdin.readline().split(' '))
    linput = list(map(int,sys.stdin.readline().split(' ')))

    count = 0
    mt = set()
    tmp = 0

    while len(mt) < N and len(linput) > tmp:
        mt.add(linput[tmp])
        tmp = tmp + 1

    # 처음은 멀티탭이 비어있으니, 일단 꽂음.
    # 중복된 건 꽂을 필요 없으니 중복 제거하여 꽂음
    for i in range(tmp,len(linput)):

        hubo1 = linput[i+1:]
        # 다음에 꽂을 전자기기 중복 제거, 순서 유지
        hubo = []
        [hubo.append(v) for v in hubo1 if v not in hubo]
        mtl = list(mt)
        #집합 인덱싱을 위해 리스트로 변환

        if linput[i] in mt:
            if linput[i] not in hubo:
                mt.remove(linput[i])
                mtl.remove(linput[i])
                #이미 있는 건데 이제 안 써? 뽑아
            continue
            #이미 있으면 그냥 지나감

        for j in range(len(mtl)):
            if mtl[j] not in hubo:
                mt.remove(mtl[j])
                mtl.remove(mtl[j])
                break
        #이제 꽂을 일 없는 전자기기는 빼버림
        hubo.reverse()
        if len(mt) == N: # 그래도 자리가 없으면
            for j in range(len(hubo)):
                if hubo[j] in mt:
                    mt.remove(hubo[j])
                    break
            #맨 뒤에서부터 사용할 전자기기를 뺌
        if len(mt) < N:
            if linput[i] not in mt:
                mt.add(linput[i])
                count = count + 1
        else:
            print("Error")
            exit()
    print(count)