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. 더 이상 버블소트가 일어나지 않으면 결과를 출력한다.
핵심 아이디어는 이어져있는 두 작업의 순서를 교체했을 때, 선택한 두 작업을 제외한 나머지 작업으로 인한 보상금의 변화가 없다는 것이다. 따라서 이어져있는 두 작업의 순서를 교체했을 때, 두 작업에 대해서 보상금이 적어지면 스왑을 하는 방식으로 해결할 수 있다.
오늘의 교훈) 다양한 문제를 해결하자