[백준 1700 / 파이썬(Python)] 멀티탭 스케줄링

[백준 1700 / 파이썬(Python)] 멀티탭 스케줄링

문제 풀이

• 이 문제는 그리드 알고리즘이므로 문제를 풀기 위한 기준을 나누어줬다.

1. 멀티탭에 이미 전기용품이 꽂혀있을 때: continue

 

2. 멀티탭에 구멍이 남아있을 때: 전기용품을 꽂아주고 continue

 

3. 멀티탭에 구멍이 없어 전기용품을 바꿔줘야할 때:

        3-1 남은 순서 중에 계속 써야하는 전기용품이 없을 때: 멀티탭에서 뺄 전기용품의 위치를 바꾸어준 뒤 break

        3-2 계속 전기용품을 써야할 때: 이후 순서에서 써야하는 전기용품 중 가장 멀리있는 것으로 위치를 바꾸고, 멀티탭에서 뺄 전기용품의 위치를 바꾸어준다.

 

 

 

틀린 풀이

idx와 farN의 초기화가 진행되지 않아 27%에서 틀렸다.

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


plug = []
count = 0
idx = 0 # 멀티탭에서 뺄 전기용품의 위치
farN = 0 # 써야하는 전기 용품 중 가장 먼 것의 위치

for i in range(k):
    if orderArr[i] in plug: # 멀티탭에 이미 꽂혀있음
        continue 
      
    if len(plug) < n:  # 멀티탭에 구멍이 남아있을 때
        plug.append(orderArr[i])
        continue 
    
    for j in range(n): #멀티탭에 전기용품 플러그를 바꿔줘야할 때
        if plug[j] not in orderArr[i:]: #남은 순서 중에 계속 써야하는 전기용품이 없을 때
            idx = j
            break
        else:
            if farN < orderArr[i:].index(plug[j]): #계속 써야하는 전기용품이 있을 때 
              farN = orderArr[i:].index(plug[j])
              idx = j
    plug[idx] = orderArr[i]
    count += 1
print(count)

 

맞은 풀이

for문 안으로 넣어주어 초기화를 해주자 문제 풀이가 맞았다.

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

plug = []
count = 0

for i in range(k):
    if orderArr[i] in plug: # 멀티탭에 이미 꽂혀있음
        continue 
      
    if len(plug) < n:  # 멀티탭에 구멍이 남아있을 때
        plug.append(orderArr[i])
        continue

    
    idx = 0 # 멀티탭에서 뺄 전기용품의 위치
    farN = 0 # 써야하는 전기 용품 중 가장 먼 것의 위치
    
    for j in range(n): #멀티탭에 전기용품 플러그를 바꿔줘야할 때
        if plug[j] not in orderArr[i:]: #남은 순서 중에 계속 써야하는 전기용품이 없을 때
            idx = j
            break
        else:
            if farN < orderArr[i:].index(plug[j]): #계속 써야하는 전기용품이 있을 때 
              farN = orderArr[i:].index(plug[j])
              idx = j
    plug[idx] = orderArr[i]
    count += 1
print(count)