문제
https://school.programmers.co.kr/learn/courses/30/lessons/42891
- 1번 음식부터 오름차순으로 1초씩 음식을 먹음
- K초 후 몇 번 음식을 먹고 있는가?
- 더 섭취할 음식이 없다면 -1 반환하기
주요 아이디어
- {음식번호 : 소요시간} 딕셔너리 형태로 저장
- 오름차순으로 돌려가며 하나씩 빼주고, K초 후를 계산해준다
코드 구현 (Python 3)
def solution(food_times, k):
answer = 0
# dict 추가
food_dict = {}
for idx, time in enumerate(food_times):
food_dict[idx] = time
idx = 0
# k번 반복
while k:
if food_dict[idx % len(food_times)] == 0:
idx += 1
continue
else:
food_dict[idx % len(food_times)] -= 1
k -= 1; idx += 1
return idx % len(food_times) + 1
시간초과....
실패 원인
- 하나씩 빼주는 방식으로는 계속 시간초과가 발생
- 다른 방법이 필요
- 풀이 방법이 떠오르지 않아서 유튜브 풀이 영상을 참조했다
https://www.youtube.com/watch?v=zpz8SMzwiHM
하나씩 돌려가면서 빼주지 말고, 소요시간에 따른 오름차순 정렬을 진행한 후 한꺼번에 빼주자
이런 식으로 묶음으로 빼주면 시간 효율성을 대폭 향상시킬 수 있다
코드 재구현 (Python 3)
import heapq
def solution(food_times, k):
# 애초에 먹을 음식 안남으면 -1 반환
if k >= sum(food_times):
return -1
food_list = []
length = len(food_times) # 남은 음식 개수
for i in range(length):
# (남은 시간, 음식 번호)
# 최소 힙을 통한 음식 시간 정렬
heapq.heappush(food_list, [food_times[i], i+1])
time = 0
# 블럭 단위로 뺄만큼 K가 남았다면 -> 묶음 단위로 빼주기
while (food_list[0][0] - time) * length < k:
k -= (food_list[0][0] - time) * length
time += food_list[0][0] - time
length -= 1
heapq.heappop(food_list)
# 최종적으로 K초에 몇 번째 음식이 오는지 구하기
result = sorted(food_list, key = lambda x: x[1])
answer = result[k % length][1]
return answer
제출 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 징검다리 (0) | 2025.01.22 |
---|---|
[프로그래머스] 요격 시스템 (0) | 2024.06.25 |
[프로그래머스] 단속 카메라 (0) | 2024.06.25 |
[LeetCode] Add Two numbers (0) | 2024.06.25 |
[프로그래머스] 문자열 압축 (0) | 2024.06.25 |