Py) 프로그래머스 42891 무지의 먹방

https://programmers.co.kr/learn/courses/30/lessons/42891?language=python3 

코딩테스트 연습 - 무지의 먹방 라이브

 

1차 시도: 시간을 못쟀지만 1시간 넘김... 

2차 시도: 12분

3차: 

 

0. 입출력

 

0.1 테스트 케이스 추가

[4,2,3,6,7,1,5,8] 16

 

 

1. 김예고리즘

1.1 로직

1. food_times의 원소를 -1 씩 계산하는 것을 k만큼 다 처리한 뒤
2. 0이 아닌 다음 음식을 찾는다. 

-> 생각하지 못한 것: 
반복문 내에서 음식이 없으면 그 다음 음식으로 넘어갈때 continue를 사용했는데, 그러다보니 음식을 먹지 않았는데 먹은 셈 치게 되어버림(반복문이 그 다음 인덱스로 넘어가면 안되는데 넘어가버림)

 

1.2 코드 -> 틀림,,

import heapq
def solution(food_times, k):
    answer = 0

    if sum(food_times)<=k:
        return -1
    q = []

    for i in range(len(food_times)):
        heapq.heappush(q,(food_times[i],i+1))  # heap에 넣어줌, (추가 대상, 추가할 원소)
        # 최소힙

    total_time=0  #전체 걸린 시간
    prev=0
    length=len(food_times)

    while total_time+(q[0][0]-prev)*length<=k:   # 음식 다 먹는데 걸리는 시간이 k이하일때
        # 음식 - prev는 한바퀴 돌때를 고려한 것
        now = heapq.heappop(q)[0]
        total_time += (now-prev)*length
        length -= 1
        prev = now
    res=sorted(q,key=lambda x:x[1])  #번호순으로 정렬

    return res[(k-total_time)%length][1]

print(solution([4,2,3,6,7,1,5,8],16))

틀린 것도 틀린건데 효율성 절대 통과 못함

 

 

2. Solution

2.1 사용 알고리즘: 우선순위 큐 (사용 자료구조: Heap)

 

2.2 로직

1) food_times로 최소힙을 구현한다. (걸리는 시간이 가장 작은거 부터 먹음)
2) heap에서 하나씩 pop한 뒤, 해당 음식을 다 먹는데 걸리는 시간이 이전에 사용한 시간과 합해서 k값보다 작은 경우에 한 해서 음식을 다 먹게 한다
3) 다 먹은 후 남은 음식끼리 정렬, % 계산으로 다음 순서 구해서 출력

 

2.3 코드

import heapq
def solution(food_times, k):
    answer = 0
    if sum(food_times)<=k:
        return -1
    q=[]
    for i in range(len(food_times)):
        heapq.heappush(q,(food_times[i],i+1))
    total_time=0  #전체 걸린 시간
    prev=0
    length=len(food_times)
    while total_time+(q[0][0]-prev)*length<=k:   #음식 다먹는데 걸리는 시간이 k이하일때
        now=heapq.heappop(q)[0]
        total_time+=(now-prev)*length
        length-=1
        prev=now
    res=sorted(q,key=lambda x:x[1])  #번호순으로 정렬
    return res[(k-total_time)%length][1]

 

 

2.4 이해안됨..

while total_time+(q[0][0]-prev)*length<=k:   # 음식 다 먹는데 걸리는 시간이 k이하일때

- length를 곱하는데 그 이유는 원판이 한바퀴 도는 시간이기 때문인것 같음. 그럼 1번 음식은 length만큼 안걸릴수도 있는거 아닌가?

- now-prev는 왜 해주는거지?

그립읍니다..굿노트..

 

2.5 새롭게 && 리마인드

import heapq

heap

lambda : lambda는 sorted와 같이 사용. 정렬할 때 기준으로 lambda를 사용하는거임