[그리디 알고리즘11] 백준 1700번 멀티탭 스케줄링 파이썬

백준 1439 뒤집기 

 

📜 문제 

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다. 

 

🚩 입력 

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다. 

 

🌞 출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오. 

 

🥨문제 풀이 

먼저 멀티탭 구멍의 개수에 전기용품의 종류대로 담는다. 이 때 종류가 같은 전기용품일 경우 멀티탭의 한 자리만 차지한다. 그리고 멀티탭의 구멍이 다 차게되면 indx=[] 빈 리스트를 만들어 멀티탭 각 구멍에 위치한 전기용품 종류가 해당 전기용품부터 ~ 전기용품 리스트 equip 끝까지 ( equip[i:]) 인덱스가 어딘지 담는다. 만약 없다면 101을 idx에 담아 idxs 배열에 append를 한다. 수는 100까지이므로 101은 없다는 표시를 의미한다. 

 

out이라는 변수에 인덱스 위치를 담은 idxs리스트 중 가장 큰 수를 가지고 있는 (가장 멀리 있는, 또는 101이라면 해당 수가 없음) 인덱스를 담고 plug[out]=equip[i] 문을 통해 plug의 out 인덱스 위치의 수를 equip[i]로 바꾼다. ---> 즉, equip[i]라는 수는 plug 안에 들어가야 하는데 어떤 위치로 들어가야할지 정할 때 equip[i] 이후의 수들 중 현재 plug 리스트 안에 있는 인덱스들이 가장 적은 위치로 바꾸었다.

 

 

 

🥕 정답 코드 

n, k = map(int,input().split())
equip = list(map(int,input().split()))		# 전기 용품을 담은 리스트 
plug=[]					  # 멀티탭 구멍을 담는 리스트 
c=0

for i in range(k):       # 전기 용품 리스트를 for 문으로 하나씩 돌려본다.
    if equip[i] in plug:   # 만약 equip[i] 전기용품이 plug 배열 안에 있다면 if문을 떠나 for문을 계속 진행하기
        continue
    if len(plug)<n:	 # 만약 plug의 길이가 n보다 적다면 (즉, plug의 자리가 아직 남았다면)
        plug.append(equip[i])    # plug에 해당 equip[i] 전기용품을 담는다.
        continue     # 그리고 if절을 빠져나와 for문으로 돌아간다. (아래 코드 실행x) 

    idxs=[]		 # 이제 plug 배열도 자리가 꽉차고 (len(plug) == n) 해당 equie[i]가 
    for j in range(n):	# plug 배열에 없다면 ---> 이제 plug리스트에 해당 equip[i]를 넣을 자리를 찾아야 한다. 
        try: 	# equip 배열의 i부터 끝까지의 배열 중 plug[j]의 인덱스를 구하기 (없을 수도 있다. --> 그럼 except으로)	
            idx = equip[i:].index(plug[j])
        except:  
            idx = 101   # plug[j]가 equip[i:]배열 안에 존재하지 않으면 indx=101
        idxs.append(idx)  # 구한 idx를 idxs 리스트에 넣기 

    out = idxs.index(max(idxs))  # idxs 리스트 중 가장 큰 수의 idxs 배열 안의 인덱스 구하기 
    plug[out] = equip[i]    # 해당 인덱스는 곧 다른 요소를 넣어도 되는 인덱스 - equip[i]를 넣어준다.
    c += 1  	 # 변경한 횟수를 센다 
print(c)         # 총 변경한 횟수 출력

 

 

 

 

틀린 코드 

n, k = map(int,input().split())
arr = list(map(int,input().split()))
n_board=[0 for _ in range(n)]
board = [0 for _ in range(110)]

for i in arr:
    board[i]+=1

for i in range(min(n,k)):
    n_board[i] = arr[i]
    board[arr[i]] -=1

def MIN(i):
    min_i = 200
    min_index= -1
    for j in range(len(n_board)):
        if min_i > board[n_board[j]]:
            min_i = board[n_board[j]]
            min_index = j
    n_board[max(min_index,0)] = i

index = 0
for i in arr[n:]:
    if i in n_board: 
        board[i] -= 1
        continue
    else:
        index += 1
        board[i] -= 1
        MIN(i)

print(index)

print 되는 index는 답은 잘 나오는데 어딘가 오류가 있는 것 같다,,