[프로그래머스] 무지의 먹방 라이브 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

---

• 접근법 1
  • 음식 먹는데 걸리는 시간 최소 순으로 생각
    • 최소 시간 음식을 다 먹을때까지 회전이 가능
    • ex) [5,2,3,4] 인 경우 최소 2바퀴를 돌 수 있는지 
  • 이번 턴(이번 시간 - 최소 시간) 동안 모든 음식을 다 먹을 수 있는지 확인 == 회전이 가능한지
    • 못 먹는다면 남은 음식 중 답이 있다
      • 남은 음식 중 남은 시간번째가 답
• 코드1

from collections import Counter

def solution(food_times, k):
    # 네트워크 장애 발생 전 다 먹었다
    if sum(food_times) <= k:
        return -1
    
    # 각 시간 당 음식 개수
    food_cnt = Counter(food_times)
    
    # [음식시간,음식번호] 음식시간 순으로 정렬
    food = sorted([[t,i] for i,t in enumerate(food_times)])
    
    # 이전에 먹은 시간
    pre_time = 0
    # 남은 음식 개수
    res_cnt = len(food_times)
    
    # 먹어보자
    for t in sorted(food_cnt.keys()):
        # 이번 턴에 먹을 시간 
        cur_time = t - pre_time
        # 이번턴에 모든 음식 먹을 수 있는가?
        if k - cur_time*res_cnt >= 0:
            # 먹은 시간 빼기
            k -= cur_time*res_cnt
            # 더 이상 못먹는 음식 빼자
            res_cnt -= food_cnt[t]
            pre_time = t
        else:
            break
    
    # 남은 음식들 인덱스 순으로 정렬
    food = food[-res_cnt:]
    food.sort(key = lambda x:x[1])
    # 남아있는 음식 중 k번째 음식 먹자
    return food[k%res_cnt][1]+1

 

• 접근법 2
  • 접근법 1 코드가 효율성 시간이 크게 나왔다 -> 줄여보자 
  • '한번에 최대 섭취할 수 있는 시간'만큼 먹어보자
  • ex) k = 10, 남은 음식 3 -> 최소 3번의 턴이 돌 수 있다 == 각 음식 당 최소 3을 섭치 가능하다
  • 모든 음식을 돌면서 
    • 먹을 수 있는 음식 중
      
      • 해당 음식의 시간이 넉넉하다 == '한번에 최대 섭취할 수 있는 시간'보다 많거나 같다
        • '한번에 최대 섭취할 수 있는 시간'만큼 먹자
      • 해당 음식의 시간이 넉넉하지 않다 == '한번에 최대 섭취할 수 있는 시간'보다 적다
        • 남은 시간 만큼만 먹고 못 먹는 음식으로 표시
  • 반복하면서
    • 남은 음식이 없으면 -1
    • 남은 음식이 있는데 한번씩 먹을 시간이 없다면 
      • 먹을 수 있는 음식 중 (남은 시간)번째 음식 번호가 답
• 코드 2

def solution(food_times, k):
    # 전체 음식 개수
    n = len(food_times)
    
    # 남은 음식의 개수
    res_foods_cnt = len(food_times)
    
    while True:
        # 남은 음식이 없다? -> -1
        if res_foods_cnt == 0:
            return -1
            
        # 남은 음식들로 최대 돌 수 있는 바퀴 == 한 번에 섭취할 시간
        rotation_time = k // res_foods_cnt
        
        # 한바퀴도 못 돌면
        if rotation_time == 0:
            break

        # 음식 회전
        for i in range(n):
            # 먹을 수 있는 음식인가? == 음식에 시간이 남았는가?
            if food_times[i] > 0:
                
                # 이번 턴에 한번에 섭취할 시간만큼 먹을 수 있는가?
                if food_times[i] > rotation_time:
                    # 먹자
                    food_times[i] -= rotation_time
                    k -= rotation_time
                    
                # 못 먹는다 == 시간이 남는다
                else:
                    k -= food_times[i]
                    food_times[i] = 0
                    # 다 먹은 음식 수 체크
                    res_foods_cnt -= 1
    
    # 음식이 남았다
    for i in range(n):
        if food_times[i] > 0:
            if k == 0:
                return i + 1
            k -= 1