코딩테스트 연습 - 더 맵게 (못 품)

[문제]

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

---

[풀이]

이 문제는 heap 정렬을 사용해서 푸는 문제인 듯 한데, 아직 안배운 개념이라 그냥 배열로 풀어보려고 했다.

 

음식 스코빌 지수 리스트를 받아서 가장 낮은 스코빌 지수가 K가 될 때 까지 문제에서 제시한 섞기를 반복하면 되는 쉬운 문제처럼 보였기 때문이다. 

 

while문과 if else문 하나씩이면 충분할거라고 생각했는데 

 

효율성에서 통과를 못했다. 

 

def solution(scoville, K):
    answer = 0
    while min(scoville) <= K: # 최소값이 K와 같거나 커지면 정지
        scoville = sorted(scoville, reverse = True) # 역순으로 정렬
        if len(scoville) < 2: # 남은 음식이 하나뿐이면 정지
            break
        else:
            scoville.append(scoville.pop()+(scoville.pop()*2)) # 섞기
            scoville = sorted(scoville, reverse = True) # 섞은 음식 포함해서 재정렬 
            answer += 1 # 섞은 횟수
        
    return -1 if min(scoville) < K else answer

이런 문제는 각 알고리즘이나 자료구조의 시간복잡도와 공간복잡도에 대한 이해가 선행되어야 할 탠데...

 

아직 효율성을 어떻게 높일 지에 대해서는 잘 모르기때문에 더 배움이 필요하다. 

 

리스트 pop 메써드의 한계인거 같기도하고.. 여기까지만 해두고 다음에 heap 정렬을 배우고 나서 다시 도전해봐야겠다.