[그리디 알고리즘] ★ 1700번 - 멀티탭 스케줄링

[백준] 1700번 - 멀티탭 스케줄링

(풀이1) 실패 코드

1) 문제 해결 아이디어

첫번째 오류. if문 검사 순서 문제

1. 멀티탭에 빈 구멍이 있을 경우 코드

2. 멀티탭에 현재 플러그가 있는 경우 코드

이런 순서로 검사를 하면 잘못된 코드가 된다.

 

예를 들어, 입력이 아래과 같다고 하면

2 7

2 2 2 3 1 2 7

1번 조건을 먼저 검사하게 되면 [2, 2] 이런식으로 같은 숫자가 중복으로 들어가게 되는 문제가 있을 수 있다. if문에서는 검사할 조건 순서를 신중하게 설정하자!!!!!

 

두번째 오류. order 슬라이싱 인덱스 문제

처음엔 현재 플러그(pivot) 기준으로 뒤 순서에 있는 플러그들에 대해서만 검사하도록 order[i+1: ] 으로 코드를 짰는데, 런타임 에러가 났다. 생각해보니 i가 k-1이 됬을 때 i+1이 k가 되어 인덱스 범위를 넘어서게되므로 오류가 났던 것이다.

 

2) 소스코드

n, k = map(int, input().split())  # 구멍개수, 총 사용횟수
order = list(map(int, input().split()))  # 사용 순서
multitap = [0] * n  # 구멍 개수만큼 초기화
cnt = 0    # 픓러그 빼는 횟수

for i in range(k):
  pivot = order[i]  # 꽂아야 할 현재 플러그
  
  # 1. 멀티탭에 빈 구멍이 있을 경우
  if(0 in multitap):
    multitap[multitap.index(0)] = pivot
  # 2. 멀티탭에 현재 플러그가 있는 경우
  elif(pivot in multitap):
    continue
  # 3. 멀티탭에 현재 플러그가 없는 경우
  else:
    max_idx = 0   # 멀티탭 플러그 중 가장 늦게 사용되는 순서 인덱스
    plug_idx = 0   # 멀티탭에 꽂을 위치 인덱스 
    
    # 멀티탭 플러그들에 대해 
    for j in range(n):
      # 멀티탭 플러그가 더이상 사용되지 않으면
      if(multitap[j] not in order[i+1:]):
        plug_idx = j  # 뺄 플러그 지정 후 탈출
        break
      # 멀티탭 플러그에서 가장 늦게 사용되는 플러그 인덱스 구하기
      elif(max_idx < order[i+1:].index(multitap[j])):
        max_idx = order[i+1:].index(multitap[j])  # 사용 순서 인덱스
        plug_idx = j  # 멀티탭 인덱스
    # plug-in, plug-out     
    multitap[plug_idx] = pivot
    cnt += 1  # 뺀 횟수 증가
print(cnt)

(풀이2) 정답 코드

1) 문제 해결 아이디어

플러그를 빼는 횟수를 최소한으로 하기 위한 방법은 다음과 같다.

멀티탭이 꽉 차있다면 현재 꽂아야할 플러그(pivot)를 포함한 뒤 순서들에서 가장 나중에 쓰이는 플러그를 (plug-out)뽑아야한다.

 

<플러그를 꽂을 때 경우>

1. 멀티탭에 해당 플러그가 있는 경우

- continue(다음 플러그 검사하기)

2. 멀티탭에 빈 구멍이 있을 경우

- 빈 곳에 넣기

3. 멀티탭에 해당 플러그가 없을 경우

- 멀티탭에서 plug-out 할 플러그(인덱스) 선택

- 멀티탭에서 플러그 plug-out, 현재 플러그(pivot) plug-in

 

2) 소스코드

n, k = map(int, input().split())  # 구멍개수, 총 사용횟수
order = list(map(int, input().split()))  # 사용 순서
multitap = [0] * n  # 구멍 개수만큼 초기화
cnt = 0    # 픓러그 빼는 횟수

for i in range(k):
  pivot = order[i]  # 꽂아야 할 현재 플러그
  
  # 1. 멀티탭에 현재 플러그가 있는 경우
  if(pivot in multitap):
    continue
  # 2. 멀티탭에 빈 구멍이 있을 경우
  elif(0 in multitap):
    multitap[multitap.index(0)] = pivot
  # 3. 멀티탭에 현재 플러그가 없는 경우
  else:
    max_idx = 0   # 멀티탭 플러그 중 가장 늦게 사용되는 순서 인덱스
    plug_idx = 0   # 멀티탭에 꽂을 위치 인덱스 
    
    # 멀티탭 플러그들에 대해 
    for j in range(n):
      # 멀티탭 플러그가 더이상 사용되지 않으면
      if(multitap[j] not in order[i:]):
        plug_idx = j  # 뺄 플러그 지정 후 탈출
        break
      # 멀티탭 플러그에서 가장 늦게 사용되는 플러그 인덱스 구하기
      elif(max_idx < order[i:].index(multitap[j])):
        max_idx = order[i:].index(multitap[j])  # 사용 순서 인덱스
        plug_idx = j  # 멀티탭 인덱스
    # plug-in, plug-out     
    multitap[plug_idx] = pivot
    cnt += 1  # 뺀 횟수 증가
print(cnt)

 

[참고] https://angangmoddi.tistory.com/165

백준 1700. 멀티탭 스케줄링(파이썬)