[CodeUp][Python]3018번 풀이

오늘은 3018번 풀이를 진행해보겠습니다. 많이 어렵진 않은데요. 아무래도 특정 원소를 기준으로 정렬하는 구현이 생소하실지도 모르겠습니다. 천천히 진행해봅시다.

 

문제 링크 : https://codeup.kr/problem.php?id=3018 

쿨식스

코드 : 

import sys

def counting_sort(store_list : list, price_list : list):
    cnt = [0 for i in range(1,100001)]
    for i in price_list:
        cnt[i] += 1
    for i in range(len(cnt)-1):
        cnt[i+1] += cnt[i]
    for i in range(len(price_list)):
        store_list[i].append(store_list[i][1]+cnt[price_list[i]])
    return store_list

n = int(sys.stdin.readline())
store_list = []
price_list = []
for i in range(n):
    num,distance,price = map(int, sys.stdin.readline().split())
    store_list.append([num,distance,price])
    price_list.append(price)
store_list = counting_sort(store_list, price_list)
unreasonable_list = sorted(store_list, key=lambda x : (x[3], x[1]))
answer = f'{unreasonable_list[0][0]} {unreasonable_list[0][1]} {unreasonable_list[0][2]}'
print(answer)
#O(n)

어째 최근에 계속 정렬 문제만 풀다보니 이번에도 counting sort를 사용해봤는데요. 음수가 나오거나 범위는 큰데 데이터 갯수가 작은게 아니라면 상당히 쓸만합니다. 시간복잡도가 O(n)으로 상당히 빠르다는 것도 한 몫 하죠. 참고로 정렬 알고리즘을 써야 하는 이유는 비합리성이 '거리 + 가격'이 아닌 '거리 순위 + 가격 순위'라서 그렇습니다.

 

저 같은 경우는 정렬 알고리즘을 이용해서 아예 거리와 가격 순위를 더한 데이터를 미리 추가한 다음 해당 데이터로 오름차순 정렬을 먼저 하고 거리에 따른 오름차순 정렬을 한 번 더 진행했습니다. 직접 구현을 하게되면 분명히 힘들겠지만 저렇게 기능을 지원하니 상당히 편하게 코드를 짤 수 있었습니다. 답의 출력은 f-string법으로 출력하면 슬라이싱을 이용한다거나 print(,end = '  ') 등의 구현을 할 필요없으니 보다 깔끔하게 짤 수 있겠죠?

 

문제 자체는 그렇게 어렵지 않습니다만 어떻게 하면 쉽게 구현할까에 대한 고민은 좀 많이 했던 문제였습니다. 제 코드가 꼭 정답은 아니니 본인만의 방법으로 풀어보시고 이렇게 푸는 사람도 있구나 하고 생각하시면 될 것 같습니다.