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

자세한 문제 내용은

아래 링크로 가주세요.

www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

접근 방법

---

일단 문제는 플러그를 빼는 횟수를 최소한으로 해서 그 회수를 출력하는 문제입니다.

자 그럼 차근차근 풀어나가 봅시다.

from sys import stdin
N, K = stdin.readline().split()
N = int(N)
K = int(K)
multap = [0] * N
li = list(map(int, stdin.readline().split()))
res = swap = num = max_I = 0

일단은 N, K를 입력받고, li리스트에 전기용품들을 입력받읍시다.

그리고 multap리스트를 N의 크기만큼 0을 채워서 생성합시다.

끝에는 코드에서 사용할 여러가지 변수인데 차차 설명하겠습니다.

 

일단 멀티탭에 콘센트를 꽂을 때 케이스가 세 가지로 분류됩니다.

1. 멀티탭에 해당 전기용품이 이미 꽂혀있을 경우

이때는 아무 작업도 하지않고 pass해서 다음 전기용품으로 넘어가 주면 됩니다.

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

이때는 그냥 빈 공간에 전기용품을 꽂아주기만 하면 됩니다.

3. 멀티탭에 빈 공간이 없을 경우

여기가 가장 중요한데 여기서도 케이스가 두 가지로 분류됩니다.

 1) 멀티탭에 꽂혀있는 전기용품 중 이후로 사용하는 것이 없는 경우

 2) 멀티탭에 꽂혀있는 전기용품이 이후에도 사용되는 경우

 

3-1번의 경우 사용하지 않는 전기용품을 뽑고 새로운 전기용품을 꽂아주도록 해주면 됩니다.

3-2번의 경우 꽂혀있는 전기용품 중 가장 나중에 사용하는 전기용품을 뽑고 새로운 전기용품을 꽂아주도록 해주면 됩니다.

 

for i in li:
    if i in multap:
        pass
    elif 0 in multap:
        multap[multap.index(0)] = i
    else:
        for j in multap:
            if j not in li[num:]:
                swap = j
                break
            elif li[num:].index(j) > max_I:
                max_I = li[num:].index(j)
                swap = j
        multap[multap.index(swap)] = i
        max_I = swap = 0
        res += 1
    num += 1
print(res)

이 부분의 소스코드는 이렇게 작성했습니다.

 

일단 for문을 사용해 li리스트의 요소를 하나씩 읽으면서 진행합니다.

그리고 if문을 사용해 1번의 경우 멀티탭에 이미 꽂혀있으니 pass합니다.

 

2번의 경우 멀티탭에 빈 공간이 있으니 멀티탭에 전기용품을 꽂아줍니다.

 

3번의 경우 for문을 사용해 multap리스트의 요소를 하나씩 읽어옵니다.

(3-1)그리고 해당 요소가 li리스트에 존재하지 않으면 그 값을 swap변수에 저장하고 break문으로 for문을 빠져나갑니다.

여기서 저는 num변수를 사용해서 li리스트를 부분적으로 사용했습니다.

 

(3-2)반대로 해당 요소가 li리스트에 존재한다면 그 요소의 인덱스 값을 구합니다.

그 값이 이전에 구했던 인덱스 값보다 더 크다면 max_I값을 새롭게 초기화한 뒤, swap에 요소의 값을 저장합니다.

for문이 종료되면 multap리스트에서 swap값의 인덱스를 구해 새로 들어갈 전기용품으로 값을 바꿔줍니다.

그리고 max_I와 swap은 다음 루프에서 사용해야 되니 0으로 초기화시키고, 전기용품을 변경했으니 res값을 1 증가시킵니다.

 

조건문이 끝나면 num변수를 1 증가시키고 루프를 반복합니다.

이 과정을 모두 끝내고 res값을 출력시키면 정답이 출력됩니다.

전체 소스코드는 아래에 있습니다.

from sys import stdin
N, K = stdin.readline().split()
N = int(N)
K = int(K)
multap = [0] * N
li = list(map(int, stdin.readline().split()))
res = swap = num = max_I = 0
for i in li:
    if i in multap:
        pass
    elif 0 in multap:
        multap[multap.index(0)] = i
    else:
        for j in multap:
            if j not in li[num:]:
                swap = j
                break
            elif li[num:].index(j) > max_I:
                max_I = li[num:].index(j)
                swap = j
        multap[multap.index(swap)] = i
        max_I = swap = 0
        res += 1
    num += 1
print(res)