[알고리즘][Python] 백준(BOJ) 1700 멀티탭 스케줄링_파이썬

 

1700 멀티탭 스케줄링    https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

 

 

 

 

문제 풀기 전 공부할 것 : 그리디 알고리즘

 

 

 

 

 

 

 

 

풀이 1

<내용>

• 전기용품의 이름 list인 kind를 for문으로 돌면서
  • kind[i]가 이미 plug에 꽂혀있으면 continue로 넘어간다.
  • plug에 구멍이 남아있으면 kind[i]를 꽂고 넘어간다.
  • kind[i]가 plug에 꽂혀있지 않으면서 plug에 구멍이 남아있지 않다면
    • idx를 저장할 idxs list를 만들고
    • plug에 들어있는 전기용품들이 다음 사용 순서가 언제인지 알아낸다.
    • 만약 다음 사용 순서가 없다면 총 사용 횟수의 최댓값이 100이기 때문에 그것보다 큰 101로 저장한다.
    • plug_out을 idxs list의 가장 큰 index로 정하고(다음 사용 순서가 없거나 가장 멀리 있기 때문에) plug에서 delete 한다.
    • plug에 kind[i]를 추가하고
    • cnt(플러그 빼는 횟수)에 1을 더한다.

 

 

 

<코드>

n, k = map(int, input().split())
kind = list(map(int, input().split()))
plug = []
cnt = 0

for i in range(k):
    if kind[i] in plug:
        continue
    if len(plug) < n:
        plug.append(kind[i])
        continue
        
    idxs = []
    for j in range(n):
        try:
            idx = kind[i:].index(plug[j])
        except:
            idx = 101
        idxs.append(idx)
    
    plug_out = idxs.index(max(idxs))
    del plug[plug_out]
    plug.append(kind[i])
    cnt += 1
print(cnt)

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 풀이 1의 내용과 동일
• 만약 다음 사용 순서가 없다면 총 사용횟수의 최댓값이 100이기 때문에 그것보다 큰 101로 저장한다.
• 이때, 이 index를 plug_out으로 정하면 되기 때문에 for문을 마저 돌지 않고 break로 빠져나오면 된다.

 

 

<코드>

n, k = map(int, input().split())
kind = list(map(int, input().split()))
plug = []
cnt = 0

for i in range(k):
    if kind[i] in plug:
        continue
    if len(plug) < n:
        plug.append(kind[i])
        continue
        
    idxs = []
    flag = True
    for j in range(n):
        try:
            idx = kind[i:].index(plug[j])
        except:
            idx = 101
            flag = False
        idxs.append(idx)
        if not flag:
            break
    
    plug_out = idxs.index(max(idxs))
    del plug[plug_out]
    plug.append(kind[i])
    cnt += 1
print(cnt)

 

 

 

 

 

 

 

시도 1 ==> 복잡하게 생각함

<내용>

• idx = max(kind_dict[plug[j]])로 잡으면 오류가 발생 → 가장 가까운 index가 아닌 가장 마지막인 사용 순서를 저장함
  • 입력
    • 3 14
    • 1 4 3 2 5 4 3 2 5 3 4 2 3 4
  • 답이 4이지만 5를 출력함
    • 1 4 3
    • 2 4 3
    • 5 4 3
    • 5 2 3
    • 4 2 3
    • 으로 4번만 빼면 가능함

 

 

 

<코드>

n, k = map(int, input().split())
kind = list(map(int, input().split()))
kind_dict = {}
for i in range(k):
    if kind[i] in kind_dict:
        kind_dict[kind[i]].append(i)
    else:
        kind_dict[kind[i]] = [i]

plug = kind[:n]
cnt = 0

if len(kind_dict) <= n:
    print(cnt)
else:
    for i in range(n, k):
        if kind[i] in plug:
            continue
        idxs = []
        for j in range(n):
            idx = max(kind_dict[plug[j]])
            if idx < i:
                idx = 101
            idxs.append(idx)
            
        plug_out = idxs.index(max(idxs))
        del plug[plug_out]
        plug.append(kind[i])
        cnt += 1
    print(cnt)

 

 

 

 

 

 

 

 

시도 2 ==> 같은 전기용품은 플러그를 2번 꽂을 필요가 없음

<내용>

• plug = kind[:n]에서 kind[:n] 안에 있는 숫자가 모두 다르지 않을 때 오류가 발생할 수 있음
  • 입력
    • 3 11
    • 11 8 11 7 2 8 2 7 5 10 2
  • 답이 3이지만 4를 출력함
    • 11 8 7
    • 8 7 2
    • 8 2 5
    • 8 2 10
    • 으로 3번만 빼면 가능함

 

 

 

<코드>

n, k = map(int, input().split())
kind = list(map(int, input().split()))
plug = kind[:n]
cnt = 0

for i in range(n, k):
    if kind[i] in plug:
        continue
    idxs = []
    for j in range(n):
        try:
            idx = kind[i:].index(plug[j])
        except:
            idx = 101
        idxs.append(idx)
    
    plug_out = idxs.index(max(idxs))
    del plug[plug_out]
    plug.append(kind[i])
    cnt += 1
print(cnt)