[Python]프로그래머스 코딩테스트연습 더 맵게

 

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

문제는 간단하다. 스코빌지수 K이하의 음식이 있으면 가장 덜 매운음식과 두번째로 덜 매운 음식 * 2 를 섞어서 다시 넣어준다. 섞었을때 쓴 음식은 다 써서 사라진다. 

가장 간단히 떠오르는 방법은 sort를 써서 구현하는 것.

scoville.sort() # 리스트가 오름차순으로 정렬된다.
new_food = scoville[0] + scoville[1] * 2 # 가장 덜 매운음식과 두번째로 덜 매운음식 * 2가 새로운 음식이 된다
scoville.append(new_food) # 새로만든 음식이 리스트에 추가된다

기본적인 틀은 이렇고 해당 과정에 조건문을 붙여 반복해주면 아주 쉽게 완성된다.

하지만 이 경우 새로운 음식을 넣을 때마다 sort()가 동작해서 효율성이 떨어져서 통과할수가없다.

K이하의 음식들만 모아서 리스트를 만들어도 결국 sort()를 쓰거나 일일이 숫자를 대조해서 정렬해야해서

결국엔 시간초과가 떠버린다. 경우의수 조건을 정밀하게 구현하면 시간복잡도를 확실히 줄여나갈 수 있긴했다.

 

여러번 테스트 해 본 결과 heapq를 이용하는게 가장 편리했다.

 

import heapq를 이용하여 풀어주었다. heapq의 주요 내용은 아래와 같다.

 

import heapq # heap 자료형 모듈

example_list = [] #일반 자료형

heapq.heapify(example_list) # heapq.heapfiy(heap) 을 이용하면 리스트 자료구조를 heap형태로변환해준다.

heapq.heappush(example_list, 3) # example_list에 3을 추가해준다. 해당 자료는 자동으로 heap형태에 의해 자리가 정해진다.

heapq.heappop(example_list) # heapq.heappop(heap) 은 맨 앞 원소를 제거하고 return해준다.

그리하여 heap구조 특성상 맨 앞에 최솟값이 자동으로 위치한다. 반대로 최댓값만 위치하게 할 수도 있다.

최솟값의 위치가 확정됨으로서 시간복잡도가 0수준으로 줄어들고 효율성이 올라간다.

 

사실 자료구조 강의는 기초적인 필수코스중 하나로서 강의를 들을때 자료구조형을 직접 구현해보기도 하였으나 실제로 어떻게 도움이 되는지 잘 몰랐으나 heapq를 이용하여 확 줄어든 시간을 보니 어떠한 상황에서 써야하는지 확실히 알게되어서 유익한 시간이었다.