더맵게

뭐 길게 작성할 필요없이 바로 구현 해볼 수 있을것 같아서 코드로 구현을 했다. (내 글씨 왜저러냐)

def solution(scoville, K):
    answer = 0

    while scoville[0] < K:
        scoville.sort()
        print("========================")
        print("스코빌: {}".format(scoville))
        new_scoville = scoville[0] + (scoville[1]*2)
        del scoville[0:2]
        print("스코빌: {}".format(scoville))
        scoville.append(new_scoville)
        answer+=1

    if len(scoville) < 1:
        return -1

    return answer


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

음 이렇게 하면 원하는 값은 나오는데 

코드 채점에서 탈탈 털리고말았다. 뭐 힙이나 큐를 활용해서 풀어야하는거같은데 자료구조를 응용? 이용? 해서 적용을 하지 못하겠다. 그러고보니 이전까지의 문제도 적용을 안한것같네ㅠㅠ

 

 

 

코드 리뷰

• 디버깅용 로그와 테스트 코드는 지우고 제출하는 것이 좋다.
• 오퍼레이터 사이는 한 칸 띄우고 작성하는 것이 좋다.
• 더 맵게 문제는 힙 혹은 우선순위 큐를 이용하여 푸는 문제이다. (sort를 이용하는 것보다 빠르기 때문에 효율성  테스트에서 통과할 수 있다.)
• 예외 처리 해주기

 

수정한 코드

def solution(scoville, K):
    answer = 0

    while scoville[0] < K:
        scoville.sort()
        # print("========================")
        # print("처음 스코빌: {}".format(scoville))

        # 정확성 테스트를 위해 이 부분을 예외 처리를 해주어야한다.
        # 배열의 첫번째 두번째가 존재해야함...
        try:
            new_scoville = scoville[0] + (scoville[1]*2)
            del scoville[0:2]
        except IndexError as e:
            break

        # print("스코빌: {}".format(scoville))
        scoville.append(new_scoville)
        answer += 1

    if len(scoville) < 1 or scoville[0] < K:
        return - 1

    return answer

 

 

 

힙 모듈 사용하기

Heap이란 자료구조 형태 중 하나로서 우선순위 큐를 위해 만들어진 구조이다. 코딩 테스트 문제 중 최솟값, 혹은 최댓값을 계속해서 호출해야 하는 상황인 경우 Heap 구조를 이용하여 구현하면 시간측면에서 굉장히 효율적인 구현이 가능하다.

heapq 모듈을 이용하여 힙 자료구조를 사용할 수 있다. heapq 는 내장 모듈이므로 따로 설치할 필요가 없다. 기본적으로 Min-priority-queue 구조를 가지고 있다.

import heapq

 

 

기존 배열을 Heap 구조로 - heapify()

testheap = [1,3,2,6,8,0,6]
heapq.heapify(testheap)
print(testheap)

# print 결과값 => Heap구조로 변함
[0,3,1,6,8,2,6]

 

Heap에 요소 추가하기 - heappush(배열이름, 요소)

testheap = []
heapq.heappush(testheap, 3)
heapq.heappush(testheap, 5)
heapq.heappush(testheap, 1)
heapq.heappush(testheap, -3)

print(testheap)

# print 결과값
[-3, 1, 3, 5]

 

Heap 요소를 삭제하기 - heappop(배열이름)

testheap = []
heapq.heappop(testheap)
heapq.heappop(testheap)

print(testheap)

# 결과값
[3, 5]

삭제를 해도 자동으로 힙 구조는 유지된다.

 

 

MaxHeap 구현하기

방법 1 

a = [3,5,2,4,1]
testheap = []

for i in a:
	heapq.heappush(testheap, -i)
for i in range(5):
	print(-heapq.heappop(testheap))

# print 결과
5
4
3
2
1

 

방법 2 - 튜플 이용하기

a = [3,5,2,4,1]
testheap = []
for i in a:
	heapq.heappush(testheap, (-i,i))
for i in range(5):
	print(heapq.heappop(testheap)[1])

# print 결과 =>
5
4
3
2
1

 

 

 

힙을 이용한 문제 풀이

# heap을 사용한 풀이
def solution(scoville, K):
    answer = 0

    heapq.heapify(scoville)

    while scoville[0] < K:
        try:
            heapq.heappush(scoville, heapq.heappop(scoville) + (heapq.heappop(scoville)*2))
            answer += 1
        except IndexError:
            return -1

    return answer

흐음 그렇구먼

 

Heap을 이용한 문제는 리스트 요소가 자주 추가, 삭제되면서 항상 정렬되어야할 때 많이 사용한다.