01월 13일 모각코_와팬호 6회차 결과 보고서

2021년 01월 13일 수요일 20:00~23:00

 

🔥 programmers 2단계 문제 해결 목록 🔥

 

• 더 맵게
    - 힙(Heap)
    - 저번에 효율성 실패로 인하여 다시 도전한 결과 효율성 통과를 하지 못함
    - 찾아본 결과 heapq를 사용하여 해결하면 효율성을 통과할 수 있다고 함
  
  
• 행렬의 곱셈
    - 문제의 내용은 이해했으나 코드를 구현하는데 혼란이 와서 해결 중...
    - 다음에 꼭 성공하기를..

 

---

더 맵게

 

 

문제 풀이

 

def solution(scoville, K):
    answer = 0
    
    scoville.sort() #정렬
    while scoville[0]<K:
        if(len(scoville)==1): #길이가 1이면 K이상으로 만들기 불가
            answer=-1
            break
        temp=scoville.pop(0) #가장 맵지 않은 음식의 스코빌 지수
        temp2=scoville.pop(0) # 두 번째로 맵지 않은 음식의 스코빌 지수
        scoville.append(temp+(temp2*2)) 
        scoville.sort() #정렬
        answer+=1 #섞어야 하는 횟수 +1
        
        
    return answer

 처음 while문과 list로 해결한 결과 정확성 테스트는 다 통과하였지만 효율성은 다 시간 초과로 성공하지 못하였다.
 sort를 사용한 것보다 heapq를 사용하면 더 효율적이라는 것을 검색을 통해 알게 되었다.

 

 정확성: 76.2
 효율성: 0.0

 

import heapq
def solution(scoville, K):
    answer = 0
    
    heapq.heapify(scoville) #기존 list를 힙으로 변환
    
    while scoville[0]<K: #K보다 작을때만 반복
        if len(scoville)==1: #길이가 1이면 더이상 만들 수 없음
            answer=-1
            break
        temp=heapq.heappop(scoville) 
        temp2=heapq.heappop(scoville)
        heapq.heappush(scoville, temp+temp2*2)
        answer+=1
        
    return answer

위의 코드를 heapq를 사용하여 고친 후 결과를 확인해보니 정확성 및 효율성을 다 통과하는 것을 확인할 수 있었다.

 

 1) heapq를 사용하여 기존 list를 힙으로 변환

 2) scoville의 첫 번째 값이 K보다 작을 때 반복

    2-1) scoville의 길이가 1이면 더 이상 만들 수 없으므로 answer를 -1로 바꾸고 중지

    2-2) heapq.heappop을 사용하여 scoville에서 값 두 개 가져오기

    2-3) x+y*2를 계산한 후 scoville에 추가

    2-4) answer +1

---