[백준 14908번] 구두 수선공 (Python3)

import sys
input = sys.stdin.readline

def bubble():
  swap = 0
  for i in range(N-1):
    if data[i][0]*data[i+1][1] > data[i+1][0]*data[i][1]:
      data[i],data[i+1],swap = data[i+1],data[i],1
  return swap

N = int(input())
data = [[*map(int,input().split()),i+1] for i in range(N)]
while bubble():
  pass
print(*map(lambda x:x[2],data))

버블소트로 해결하였다.

재미있는 문제였다. 아이디어를 떠올리기 약간 까다로울 수 있다.

 

풀이를 설명하면,

1. 모든 입력값을 번호와 함께 저장한다.

2. 버블소트 방식으로 양 옆의 두 작업의 순서를 교체했을 때, 시간이 단축되면 스왑한다.

3. 더 이상 버블소트가 일어나지 않으면 결과를 출력한다.

 

핵심 아이디어는 이어져있는 두 작업의 순서를 교체했을 때, 선택한 두 작업을 제외한 나머지 작업으로 인한 보상금의 변화가 없다는 것이다. 따라서 이어져있는 두 작업의 순서를 교체했을 때, 두 작업에 대해서 보상금이 적어지면 스왑을 하는 방식으로 해결할 수 있다.

 

 

오늘의 교훈) 다양한 문제를 해결하자