백준 1700 멀티탭 스케줄링 파이썬 풀이, 반례

난이도 : 골드1

풀이일 : 2404077

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

1700번: 멀티탭 스케줄링

---

문제 캡쳐

---

아이디어

• 비어있는 플러그가 있다면, 현재 사용할 제품을 그냥 연결한다.
• 비어있는 플러그가 없다면, 현재 연결 되어있는 제품의 플러그를 한 개 제거하고 제거 횟수를 센다.
  
  • 사용이 끝나 더이상 사용하지 않을 제품을 우선적으로 제거한다.
  • 사용이 끝난 제품이 없다면, 다음 사용순서가 가장 많이 남은 제품을 제거한다.

---

전체 풀이코드

import sys

N, K = map(int, sys.stdin.readline().split())
electronics = list(map(int, sys.stdin.readline().split()))
order = [[] for _ in range(K + 1)]  # 사용되는 순서
result = 0

for i in range(K):
    order[electronics[i]].append(i)

plugs = set()
for electronic in electronics:
    order[electronic].pop(0)  # 사용 제품 제거
    if electronic in plugs:  # 이미 연결되어 있는 제품이면 무시
        continue
    if len(plugs) == N:  # 플러그에 빈 자리가 없는 경우
        target = 0  # 삭제 대상
        time = 0
        for x in plugs:
            # 사용이 끝난 제품이 있을 경우
            if not order[x]:
                target = x
                time = float('inf')
            # 남은 사용 시간이 가장 긴 것, 사용 시간이 같다면 출현 빈도가 적은 것 삭제
            elif order[x][0] > time:
                target = x
                time = order[x][0]
        # 플러그를 뽑고 result 더하기
        plugs.remove(target)
        result += 1
    plugs.add(electronic)

print(result)

---

풀이 상세

N, K = map(int, sys.stdin.readline().split())
electronics = list(map(int, sys.stdin.readline().split()))
order = [[] for _ in range(K + 1)]  # 사용되는 순서
result = 0

for i in range(K):
    order[electronics[i]].append(i)

• electonics : 입력되는 전자제품들의 사용 순서 배열이다.
• order : 각 전자제품의 인덱스 배열에 해당 제품이 몇 번째로 사용되는지 순서를 기록할 배열이다.
• result : 총 몇 회 플러그를 교체하였는지 확인할 변수이다.
• for 반복문 : 각 전자제품들의 사용 순서를 보고 order 각 인덱스 배열 안에 순서를 기록해준다.

 

plugs = set()
for electronic in electronics:
    order[electronic].pop(0)  # 사용 제품 제거
    if electronic in plugs:  # 이미 연결되어 있는 제품이면 무시
        continue

• plugs : 현재 꽂혀있는 플러그가 몇 번 전자제품의 플러그인지 저장할 set이다. 중복을 피하기 위해 set을 사용하였다.
• 각 전자제품 사용 순서에 맞게 전자제품 번호를 electronic으로 선언하고, 반복문을 돈다.
• order에는 각 전자제품이 몇 번째로 사용되는지 정보가 들어 있으므로, elecronic을 재할당 할 때마다 맨 앞 순서를 삭제해준다.
• 만약 현재 전자제품이 플러그에 연결되어 있다면, 아래 과정을 반복할 필요가 없으므로 continue를 통해 다음 반복으로 넘어간다.

 

    if len(plugs) == N:  # 플러그에 빈 자리가 없는 경우
        target = 0  # 삭제 대상
        time = 0
        for x in plugs:
            # 사용이 끝난 제품이 있을 경우
            if not order[x]:
                target = x
                time = float('inf')
            # 남은 사용 시간이 가장 긴 것, 사용 시간이 같다면 출현 빈도가 적은 것 삭제
            elif order[x][0] > time:
                target = x
                time = order[x][0]
        # 플러그를 뽑고 result 더하기
        plugs.remove(target)
        result += 1
    plugs.add(electronic)

• 현재 사용할 제품이 플러그에 연결되어 있지 않고, 플러그에 빈자리가 있다면 if문을 건너뛰고 맨 아래 줄로 내려가 plugs에 제품 플러그를 꽂고 다음 반복으로 넘어간다.
• len(plugs) == N 이라면, 모든 플러그에 전자제품이 연결되어 있는 경우이므로, 다른 전자제품의 코드를 제거해야 현재 전자제품의 플러그를 연결할 수 있다.
• time : target에 저장될 전자제품이 다음 사용까지 남은 시간
• target : 플러그에서 제거할 전자제품의 번호
• for 반복문 : 현재 꽂혀있는 전자제품들에 대해 확인한다.
• if not order[x] : 다음 사용할 순서가 없다면, 즉 사용이 끝난 전자제품이라면, target에 해당 전자제품을 재할당하고, time은 무한히 큰 값으로 재할당한다.
• elif order[x][0] > time : 다음 사용 순서를 비교하여, 가장 나중 순서에 사용할 전자제품의 정보를 time, target에 저장한다.
• 반복문이 끝난 후 저장되어 있는 target을 plugs에서 제거하고, 플러그 교체 횟수를 세기 위해 result를 +1 해준다.
• 플러그를 제거해 자리가 났으므로, plugs에 제픔 플러그를 꽂는다.

 

print(result)

• 최종적으로 몇 번이나 플러그를 교체하였는지 출력한다.

---

반례

입력	출력
2 9 1 2 3 1 2 3 1 2 3	4

 

반례출처는 아래와 같습니다.

https://www.acmicpc.net/board/view/111305

글 읽기 - 테스트케이스 하나 공유합니다.

---

느낀점

• 한 시간 넘게 푼 문제인데, 진짜 재미있었다. 내 논리가 말이 되는지, 코드로 표현할 때 지금의 방법이 제일 나은 방법일 지, 시간을 줄이려면 어떤 자료구조를 사용해야 할 지 고민하면서 풀어내니까 익숙한 문제 쉽게 풀어낼때보다 훨씬 즐거웠다. 역시 문제가 어려워야 재밌지!
• 풀고 나서 solved.ac 를 확인하니까, 그리디 유형으로 들어가서 내가 안 풀었던 문제 유형 점수가 올라갔더라 괜히 더 신난다.
• 또, 코드 구조를 조금씩 따로 떼어 적는게 나도 다시 되짚어볼 수 있어서 더 좋은 것 같다. 앞으로는 전체 코드랑 부분 부분을 분리해서 기록해야지.