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

[문제]

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

[분류]

그리디 알고리즘

 

[구현 논리]

우선 N, K가 100이하이므로 시간복잡도 O(N^3) or O(K^3)까지 가능.

플러그가 비어있을 때는 그냥 추가하고

플러그가 꽉 차있을 때는 뒤에 들어올 코드를 확인해야함. (플러그에서 무슨 코드를 뽑을지)

 

코드흐름은 특정 코드에 대해 뒤에 없으면 바로 교환!

만약 플러그에 있는 모든 코드가 뒤에 다 있으면
플러그에 있는 코드 중 가장 마지막에 등장하는 코드와 교환!

 

검사함수 구현하고 for문 1번 돌리면 풀림

시간 복잡도 O(K^3)

 

[코드]

N, K = map(int, input().split())
data = list(map(int, input().split()))
house = []

def check(ind): #집에서 바꿀 원소 인덱스 반환하는 함수
  for elem_ind in range(len(house)):
    if house[elem_ind] not in data[ind+1:]: #뒤에 없으면
      return elem_ind
  maxi = -1
  for num in house:
    if maxi < data[ind+1:].index(num):
      maxi = data[ind+1:].index(num)
  return house.index(data[maxi+ind+1])

cnt = 0
for i in range(K):
  if len(house) < N: #집에 여유가 있다면
    if data[i] not in house:
      house.append(data[i])
  else: #집이 꽉찼다면
    if data[i] in house:
      continue
    else:
      cnt += 1
      index = check(i)
      house[index] = data[i]

print(cnt)

 

<피드백>

처음에 특정 코드 k에 대해 만약 플러그에 있는 모든 코드가 뒤에 다 있으면

플러그에 있는 코드 중 아무거나 빼는 것으로 알고리즘을 짜서 틀렸었음. (애매하긴 했었음)

이렇게 알고리즘을 짜면

3 9

1 4 3 2 5 2 3 5 4

의 테스트케이스에서 잘못된 답이 도출됨.

 

다음번에 맞출려면 코드 작성 전 구현 논리에서 애매한 부분이 있으면

최대한 확실히, 안전장치를 만들고 코드를 써야할 것임.

 

<기타 숙지해야할 문법>

a = [1, 2, 2, 3]

a.index(1) -> 0

a.index(2) -> 1

a[2:].index(3) -> 1