[coding_test]더 맵게

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

코딩테스트 연습 - 더 맵게

K이상으로 만들수 없는 경우 -1을 리턴한다는 것을 염두에 두고 

리스트가 어떤식으로 들어올지 모르니 정렬을 한 후 deque를 이용하여 

코드를 짜보았다. 

정확성은 올패스를 했지만 효율성에서 전부 탈락을 하게 되어 

문제를 어떻게 만들었는지 확인해보고, heapq라는 라이브러리에 대해 알게 되었다. 

def make_scobille(scoville, K, count):
    from collections import deque

    scoville=deque(scoville)
    if scoville[0] >= K:
        print('1',scoville)
        return count
    elif len(scoville) == 1:
        print('2',scoville)
        return -1
    else:
        print('3',len(scoville))
        scoville.appendleft(scoville.popleft()+(scoville.popleft()*2))
        count += 1
        return make_scobille(sorted(scoville), K, count) 


def solution(scoville, K):

    count  = 0
    scoville.sort()

    return make_scobille(scoville, K, count)

두번째 코드는 heaqp를 확인해보고 문제를 풀어봤다. 

하지만 사용방식을 몰라 계속해서 오류가 나고 생각한 방식과 많이 달라

다른사람들의 사용을 보며 공부를 하여 스스로 풀어보았다. 

def solution(scoville, K):
    import heapq
    
    cnt = 0
    heapq.heapify(scoville)
    while True:
        if len(scoville) == 1 and scoville[0] < K:  
            return -1
            break
        first_cook = heapq.heappop(scoville)
        second_cook = heapq.heappop(scoville)

        heapq.heappush(scoville,first_cook+(second_cook*2))

        cnt += 1
        if scoville[0] >= K:
            return cnt
            break

확실히 heaqp를 사용한 코드를 보면 전체적인면에서 코드과 확연하게 차이가 난다는 것을 확인 할 수 있었다. 

특히  테스트 12번에서 첫번째 코드는 20.91ms가 1.14ms로 확연하게 줄어든 모습을 확인할 수 있었다. 

---

문제풀이 후 

 

• heapq에 대해서 공부를 할 수 있었다. 
• 효율성이 커지면 빠른처리가 가능하고 데이터가 많은 부분에선 더 효과가 극대화 되는 것을 확인할 수 있었다.