[코테 연습]더 맵게 Python

나도 실제로 매운걸 굉장히 좋아한다. 특히 청양고추 청양지원

 

문제 설명

매운 것을 좋아하는 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 합니다.

---

처음엔 완전 간단하게 생각했다.

min 값을 체크해서 K보다 작으면 min값이 K보다 작을 때까지 함수를 실행해서 K보다 크게 만드는 것.

def cal(twoNum):
    return twoNum[0]+2*twoNum[1]

def check(scoville):
    twoNum = []
    for _ in range(2):
        minNum = min(scoville)
        scoville.remove(minNum)
        twoNum.append(minNum)

    newNum = cal(twoNum)
    scoville.append(newNum)

    return scoville

def solution(scoville, K):

    cnt = 0
    while min(scoville) < K:
        cnt += 1
        check(scoville)

    return cnt

print(solution(	[1, 2, 3, 9, 10, 12], 7))

정확성 테스트

테스트 1 〉	실패 (런타임 에러)
테스트 2 〉	통과 (0.04ms, 10.6MB)
테스트 3 〉	실패 (런타임 에러)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (10.10ms, 10.7MB)
테스트 7 〉	통과 (7.35ms, 10.7MB)
테스트 8 〉	실패 (런타임 에러)
테스트 9 〉	통과 (0.22ms, 10.9MB)
테스트 10 〉	통과 (5.30ms, 10.8MB)
테스트 11 〉	통과 (2.40ms, 10.8MB)
테스트 12 〉	통과 (23.00ms, 10.8MB)
테스트 13 〉	통과 (7.51ms, 10.8MB)
테스트 14 〉	실패 (런타임 에러)
테스트 15 〉	통과 (12.24ms, 10.8MB)
테스트 16 〉	통과 (0.04ms, 10.8MB)

정확성 틀렸고, 효율성은 개박살났다. 쓰레기 코드라는 뜻 ^>^!

 

---

두번째 시도

 

K보다 작은 값들만 가지고 계산을 해보기로 했다.

값을 계산한 이후에는 sort를 해서 가장 작은 값과 그담으로 작은값을 알 수 있게 하였다. 

해서,, 계산을 하는 횟수를 세고 마지막까지 모두 계산하였는데 ex. 1, 1, 1, 1 

그럼에도 불구하고 K를 넘지 못하는 경우엔 한번 더 계산 (이미 K 이상인 값과 계산을 한번만 더 하면 되니깐)

그리고 만약에 계산을 다 한 경우에 k보다 작은 수들의 모임이 전체 배열인 경우에는 전체를 다 계산해도 k를 넘을 수 없다는 결론이므로 -1

def solution(scoville, K):
    lowerNum = [i for i in scoville if i < K]

    cnt = 0
    for i in range(len(lowerNum)-1):
        cnt += 1
        lowerNum = sorted(lowerNum)
        lowerNum[i+1] = lowerNum[i] + lowerNum[i+1] * 2

    if lowerNum[-1] < K:
        cnt += 1
        if len(lowerNum) == len(scoville):
            return -1

    return cnt

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.54ms, 10.7MB)
테스트 4 〉	실패 (0.24ms, 10.7MB)
테스트 5 〉	실패 (0.17ms, 10.8MB)
테스트 6 〉	실패 (2.70ms, 10.7MB)
테스트 7 〉	실패 (2.07ms, 10.7MB)
테스트 8 〉	통과 (0.13ms, 10.8MB)
테스트 9 〉	실패 (0.22ms, 10.8MB)
테스트 10 〉	실패 (1.53ms, 10.7MB)
테스트 11 〉	실패 (0.77ms, 10.9MB)
테스트 12 〉	실패 (6.04ms, 10.8MB)
테스트 13 〉	실패 (2.03ms, 10.8MB)
테스트 14 〉	통과 (0.05ms, 10.8MB)
테스트 15 〉	실패 (3.30ms, 10.8MB)
테스트 16 〉	통과 (0.04ms, 10.8MB)

WOW 더 틀린다.. 효율성 테스트는 보나마나 였고,,  

 

 

---

세번째 시도 우선순위 큐 사용

from queue import PriorityQueue

def solution(scoville, K):
    que = PriorityQueue()

    for i in scoville:
        que.put(i)

    cnt = 0
    while que:
        sco = que.get()

        if sco < K:
            cnt += 1
            que.put(sco + que.get()*2)
        else:
            break
    return cnt

정확성 테스트

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	통과 (0.07ms, 10.8MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	통과 (0.08ms, 10.8MB)
테스트 5 〉	통과 (0.07ms, 10.6MB)
테스트 6 〉	통과 (3.82ms, 10.8MB)
테스트 7 〉	통과 (3.20ms, 10.7MB)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (0.49ms, 10.8MB)
테스트 10 〉	통과 (2.82ms, 10.8MB)
테스트 11 〉	통과 (1.93ms, 10.8MB)
테스트 12 〉	통과 (5.74ms, 10.9MB)
테스트 13 〉	통과 (3.62ms, 10.8MB)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	통과 (3.96ms, 10.9MB)
테스트 16 〉	통과 (0.06ms, 10.7MB)

아웨에에엑!!!!!!!!!!!!!!!!!!

 

---

네번째 시도 아 -1! 설정을 안해줬구나!

from queue import PriorityQueue

def solution(scoville, K):
    que = PriorityQueue()

    for i in scoville:
        que.put(i)

    cnt = 0
    while que:
        sco = que.get()

        if sco < K:
            cnt += 1
            if cnt == len(scoville)-1:
                return -1
            que.put(sco + que.get()*2)
        else:
            break
    return cnt

정확성 테스트

테스트 1 〉	통과 (0.06ms, 10.8MB)
테스트 2 〉	통과 (0.14ms, 10.8MB)
테스트 3 〉	통과 (0.11ms, 10.8MB)
테스트 4 〉	통과 (0.08ms, 10.7MB)
테스트 5 〉	통과 (0.08ms, 10.8MB)
테스트 6 〉	통과 (3.95ms, 10.8MB)
테스트 7 〉	통과 (3.22ms, 10.8MB)
테스트 8 〉	통과 (0.60ms, 10.7MB)
테스트 9 〉	통과 (0.94ms, 10.8MB)
테스트 10 〉	통과 (2.92ms, 10.8MB)
테스트 11 〉	통과 (2.05ms, 10.8MB)
테스트 12 〉	통과 (5.72ms, 10.9MB)
테스트 13 〉	통과 (3.13ms, 10.7MB)
테스트 14 〉	통과 (0.16ms, 10.8MB)
테스트 15 〉	통과 (4.31ms, 10.8MB)
테스트 16 〉	실패 (0.21ms, 10.7MB)

후,,,,뭐지?

 

---

다섯번째 트라이 ;  스코빌 지수가 딱! 들어 맞는 경우  ex. [1,2,3] K:11 

from queue import PriorityQueue

def solution(scoville, K):
    que = PriorityQueue()

    for i in scoville:
        que.put(i)

    cnt = 0
    while que:
        sco = que.get()

        if sco < K:
            cnt += 1
            que.put(sco + que.get()*2)

            if cnt == len(scoville)-1:
                if que.get() < K:
                    return -1
                else:
                    return cnt
        else:
            break
    return cnt

통과는 했는데 효율성이 통과가 즌혀 안된다.

 

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)

---

 

여섯번째 시도 heapq 모듈 사용

import heapq

def solution(scoville, K):
    if min(scoville) >= K:
        return 0

    heap = []

    for i in scoville:
        heapq.heappush(heap, i)

    cnt = 0
    while True:
        if heap[0] < K:
            if len(heap) ==1:
                return -1
            cnt += 1
            heapq.heappush(heap, heapq.heappop(heap)+heapq.heappop(heap)*2)
  
        else:
            break

    return cnt

굿뜨!

 

정확성 테스트

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.6MB)
테스트 3 〉	통과 (0.05ms, 10.8MB)
테스트 4 〉	통과 (0.04ms, 10.6MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.58ms, 10.7MB)
테스트 7 〉	통과 (0.48ms, 10.7MB)
테스트 8 〉	통과 (0.12ms, 10.6MB)
테스트 9 〉	통과 (0.09ms, 10.7MB)
테스트 10 〉	통과 (0.38ms, 10.8MB)
테스트 11 〉	통과 (0.28ms, 10.8MB)
테스트 12 〉	통과 (0.82ms, 10.9MB)
테스트 13 〉	통과 (0.46ms, 10.8MB)
테스트 14 〉	통과 (0.05ms, 10.8MB)
테스트 15 〉	통과 (0.62ms, 10.8MB)
테스트 16 〉	통과 (0.04ms, 10.6MB)

효율성 테스트

테스트 1 〉	통과 (188.32ms, 117MB)
테스트 2 〉	통과 (421.88ms, 215MB)
테스트 3 〉	통과 (1957.74ms, 706MB)
테스트 4 〉	통과 (146.13ms, 95.9MB)
테스트 5 〉	통과 (2229.32ms, 739MB)

 

priorityQueue와 heapq의 차이가 무엇일까?

 

Queue.PriorityQueue is a thread-safe class, while the heapq module makes no thread-safety guarantees.