백준 1881 공 바꾸기 파이썬 풀이

난이도 : 골드1

풀이일 : 2404081

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

1881번: 공 바꾸기

---

문제 캡쳐

---

아이디어

• 비어있는 상자가 있다면, 공을 비어있는 상자에 집어 넣고 count + 1
• 비어있는 상자가 없다면, 다음 사용까지의 시간을 비교
  • 사용이 끝난 공이 있다면, 해당 공을 제거 후, 새 공을 집어 넣고 count + 1
  • 사용이 끝난 공이 없다면, 다음 사용 시점이 가장 늦은 공을 제거 후, 새 공을 집어 넣고 count + 1
• 교체는 연산 1로 취급하기 때문에, 제거 시에는 count + 1 하지 않는다. 공 추가 시에만 count + 1 해주기

---

풀이코드 전체

import sys

n = int(sys.stdin.readline())
count = 0  # 연산 횟수
cards = []
order = [[] for _ in range(n)]  # 각 카드 등장 순서
if n:
    cards = list(map(int, sys.stdin.readline().split()))

for i in range(n):
    order[cards[i]].append(i)

boxes = set()
for card in cards:
    order[card].pop(0)  # 카드 사용 처리
    if card in boxes:  # 이미 상자에 있는 수 무시
        continue
    if len(boxes) == 4:  # 상자가 가득 찬 경우
        target = 0
        time = 0
        # 사용이 끝난 공, 가장 나중에 재사용할 공 탐색
        for ball in boxes:
            if not order[ball]:
                target = ball
                time = float('inf')
            elif order[ball][0] > time:
                target = ball
                time = order[ball][0]
        boxes.remove(target)  # 선정된 공 제거
    boxes.add(card)  # 상자에 공 추가
    count += 1  # 연산 횟수 증가

print(count)

---

풀이코드 상세

n = int(sys.stdin.readline())
count = 0  # 연산 횟수
cards = []
order = [[] for _ in range(n)]  # 각 카드 등장 순서
if n:
    cards = list(map(int, sys.stdin.readline().split()))

for i in range(n):
    order[cards[i]].append(i)

• count : 연산 횟수를 저장할 변수
• cards : 카드 등장 순서를 저장할 배열
• order : 각 카드들을 몇 번째로 사용하는지 저장할 2차원 배열
• if n : n이 0인 경우, cards 정보가 주어지지 않으므로, 조건을 걸어준다.
• for i in range(n) : 각 카드 등장 순서를 order의 해당 카드 인덱스에 저장 해준다.

 

boxes = set()
for card in cards:
    order[card].pop(0)  # 카드 사용 처리
    if card in boxes:  # 이미 상자에 있는 수 무시
        continue

• boxes : 문제에서 주어진 상자 네 개를 의미한다. 중복되는 요소를 담을 수 없기 때문에 set으로 관리한다.
• for card in cards : cards에 있는 카드들을 순서대로 card 변수에 저장하고, 반복문을 수행한다.
• order[card].pop(0) : 해당 카드를 사용했다는 의미로 order[card]의 첫 번째 사용 횟수를 삭제해준다.
• if card in boxes : 이미 상자에 해당 숫자 공이 들어있다면, 다음 반복으로 넘어간다.

 

    if len(boxes) == 4:  # 상자가 가득 찬 경우
        target = 0
        time = 0
        # 사용이 끝난 공, 가장 나중에 재사용할 공 탐색
        for ball in boxes:
            if not order[ball]:
                target = ball
                time = float('inf')
            elif order[ball][0] > time:
                target = ball
                time = order[ball][0]
        boxes.remove(target)  # 선정된 공 제거

• len(boxes) == 4 : 상자는 네 개 뿐이므로, 상자가 가득차 있는 상태를 의미한다.
• target : 삭제할 공의 숫자
• time : 삭제할 공이 사용될 순서
• for ball in boxes : 박스에 들어있는 모든 공을 하나씩 꺼내는 반복문
  • if not order[ball] : 해당 공의 사용이 끝나서 다시 사용되지 않을 경우, target을 해당 공 번호로, time을 무한대 숫자로 재할당한다.
  • elif order[ball][0] > time : 저장된 target의 재사용 순서보다 현재 공의 재사용 순서가 늦다면, target, time을 현재 공 정보로 재할당한다.
• 반복문이 끝난 후, 저장된 target을 boxes에서 제거한다. 이때, 제거 연산은 별도로 숫자를 세지 않는다.

 

    boxes.add(card)  # 상자에 공 추가
    count += 1  # 연산 횟수 증가

print(count)

• 상자에 공간이 있다면, 바로 위 코드로 내려오고, 공간이 없었다면 한 가지를 제거해 공간을 만들고 난 다음 위 코드를 만나게 된다.
• boxes에 현재 카드의 숫자 공을 추가한다. 삽입과 교체 모두 한 번의 연산으로 계산하기 위해 공 추가 시 count에 + 1을 해준다.
• 전체 연산 횟수를 출력한다.

---

느낀점

• 어제 푼 문제와 거의 같아서 쉽게 풀 수 있었다. 지금만 같으면 이런 문제 나오면 언제든지 쉽게 풀어낼 수 있을 것만 같은 기분이 든다. 
• 어제도 오늘도 풀이 후 코드를 더 깔끔하게 만들 수 있는 방법을 고민해보았는데, 조금 더 개선할 수 있을 것 같아서 다른 사람들은 어떻게 풀었는지 찾아보고, 내 코드랑 비교해보면서 개선할 수 있도록 해야지.