문제 06 : 무지의 먹방 라이브(난이도 : 1/3)

문제 출처 : 코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스 (programmers.co.kr)

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

 

---

1. 내가 생각한 풀이

• 정확성 : 25.4 / 42.9
• 효율성 : 0.0 / 57.1

### 내가 생각한 풀이 방법 ###

def solution(k):
    # 배열 입력
    food_times = list(map(int, input().split()))
    longest = food_times.index(max(food_times))
    now = 0
    i = 0

    while(now < k):
        if food_times[i] == 0:
            i += 1
            if i >= len(food_times):
                i = 0
            continue
        food_times[i] -= 1
        now += 1
        i += 1
        if i >= len(food_times):
            i = 0
        elif food_times[longest] == 0 and now < k:
            return -1

    return i
    
print("장애 복구 후", solution(5) + 1, "번 음식부터 다시 먹기 시작하면 됩니다.")

• 문제를 딱 읽고 생각나는 방법 그대로 구현했다.
• now는 현재 소요된 시간으로 문제에서 제한된 k초 이전동안 now를 증가시키며 음식을 섭취한다.
• 1초동안 음식을 섭취하면서 해당 음식의 남은 시간을 감소 시키고, k초가 지났을 때 먹어야 할 음식을 반환한다.
• longest란 이름의 변수는 음식의 리스트 중 가장 섭취 시간이 긴 음식의 인덱스를 가지는데, 만일 이 longest 인덱스의 남은 음식 섭취 시간이 0인 경우 모든 음식을 다 먹은 것이 되므로 이 때는 -1을 반환하는 것으로 구현했다.

 

• 결과는 위에 보다시피 정확도는 약 50%, 효율성은 0%를 자랑(?)하게 되었다...

---

2. 문제 풀이 해설 방법

(1) 문제 분석

1) 사용할 자료구조 선택

• 문제 유형인 그리디 알고리즘을 떠올리며 시간이 적게 걸리는 음식부터 확인하는 방식으로 해결해 갈 필요가 있다.
• 모든 음식을 시간을 기준으로 오름차순으로 정렬하고, 시간이 적게 걸리는 음식부터 제거해 나간다.
• 이를 구현하기 위해 '우선순위 큐(=최소 힙)'를 사용해야 한다.
• (우선순위 큐를 사용하면 음식의 시간을 기준으로 자동으로 오름차순으로 정렬되는 효과가 있다.)

 

2) 작은 예시를 통해 문제 해결

• 만일, 다음과 같이 3개의 음식이 있고 k=15라고 가정해보자.

• (소요 시간, 음식 번호)
• 1번 음식 : 8초 소요 -> (8, 1)
• 2번 음식 : 6초 소요 -> (6, 2)
• 3번 음식 : 4초 소요 -> (4, 3)

 

• 우선순위 큐에는 [ (4, 3), (6, 2), (8, 1) ]의 순서로 정렬될 것이다.
• (최소 힙이므로 정확하게는 완전이진트리의 형태로 정렬되지만, 이해를 쉽게 하기 위해 위와 같은 형태로 예시를 든다.)

 

• 정렬 결과, 3번 음식이 소요 시간이 가장 적으므로 3번 음식을 먼저 다 먹는다고 가정한다.
• 먼저 모든 음식은 1초동안 맛 보고 다시 돌아올 기회까지 기다려야 되기 때문에, 3번 음식을 다 먹는데 소요 되는 시간은 (3번 음식을 다 먹는데 필요한 시간) * (현재 남은 음식의 수) = 4 * 3 = 12초가 소요된다.
• 12는 k=15 보다 작기 때문에 3번 음식은 다 먹을 수 있고 남은 시간은 3초가 된다.

 

• 이제 3번 음식을 다 먹어치웠으니 다음으로 소요 시간이 적은 6번 음식에 대해 검사한다.
• 똑같이 2번 음식을 다 먹는데 소요되는 시간은 (2번 음식을 다 먹는데 필요한 시간) * (현재 남은 음식의 수) = 6 * 2 = 12초가 소요된다.
• 남은 시간은 3초인데 2번 음식을 다 먹으려면 12초가 필요해 2번 음식은 처음 k=15초 안에 다 먹을수 가 없다.

 

• 결국, 남은 3초 동안은 어떠한 짓을 해봐도 1번과 2번 음식은 다 먹어치울 수 가 없다.
• 이제는 다음으로 먹어야 할 음식의 순서를 정렬하고 k초 째 먹을 음식을 찾아야 한다.
• 그래도 남은 3초 동안 음식을 3번 맛봐야 되니 이제 4초 째 먹는 음식이 바로 문제에서 찾는 k초 째 먹을 음식이 된다.

 

• 먼저 제한 시간인 k초 안에 다 먹을 수 있는 음식을 찾기 위해서 우선순위 큐를 사용했지만, 실제 문제에서는 음식 번호 순서대로 먹게 되어 있다.
• 따라서, 이제 먹어야 할 음식을 번호 순으로 정렬하면 남은 3초 동안 다음과 같이 음식을 먹는다.

 

• 1sec : 1번 음식
• 2sec : 2번 음식
• 3sec : 1번 음식
• 4sec : 2번 음식 <- k초 째 먹어야 할 음식!

 

• 결과적으로 2번 음식을 반환하는 위 과정을 코드로 구현한다.

 

(2) 코드

import heapq

def solution(food_times, k):
    # 전체 음식을 방송 시작후 k초 이전에 다 먹는 경우 -1 반환
    if sum(food_times) <= k:
        return -1

    # 시간이 적은 음식 부터 섭취(우선순위 큐 이용)
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호)의 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1)) # 음식 번호 = 인덱스 + 1

    # 먼저, 우선순위 큐에 있는 가장 시간이 적은 음식을 다 먹는데 걸리는 시간이 n초라고 가정한다.
    # (n * 남은 음식의 개수)가 k보다 작을 경우, 해당 음식은 k초 전에 다 먹을 수 있다.
    # 그리고 다른 음식들은 남은 시간이 (n * 남은 음식의 개수)만큼 줄어든다.
    # 남은 음식들 중 가장 먹는데 시간이 적은 음식에 대해 위 과정을 반복한다.
    # 반복하다가 지금까지 누적된 남은 음식을 다 먹는데 걸리는 시간이 k를 넘어가는 것으로 예측되면 반복을 멈춘다.

    sum_value = 0 # 음식을 먹기 위해 사용된 누적 시간
    previous = 0 # 이전에 소요시간이 가장 짧은 음식을 다 먹기 위해 소요된 시간
    length = len(food_times) # 남은 음식의 총 갯수

    # q[0][0] : 우선순위 큐에서 섭취 시간이 가장 작은 음식의 남은 섭취 시간
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0] # 우선순위 큐에서 음식을 꺼내고 음식의 남은 섭취시간 저장

        sum_value += (now - previous) * length # 지금까지 음식을 먹는데 걸린 누적시간 저장
        # 위 과정에서 하나의 음식은 다 먹은 것으로 처리가 된다.

        length -= 1 # 남은 음식의 개수를 줄임
        previous = now # 음식을 다 먹었으므로 이전에 음식을 다 섭취하는데 소요된 시간으로 새롭게 설정

    # 이제 남은 음식들 중 몇 번째 음식을 먹어야 되는지 확인
    result = sorted(q, key = lambda x: x[1]) # 음식 번호를 기준으로 정렬
    # 현재 result에 이미 음식을 다 먹은 것들은 삭제되어있다.
    # reuslt = [(음식 시간, 음식 번호), ...]
    return result[(k - sum_value) % length][1]

• 처음에 while문의 조건인 sum_value + ( ( q[0][0] - previous ) * length ) <= k 부분과
• k번째 먹어야 할 음식을 구해야 하는 부분인 return 구문이 조금 까다롭다.
• 최대한 주석과 코드의 진행을 보면서 이 글을 읽는 다른 분들도 이해할 수 있으리라 기대한다.

---

3. 후기

  일단 처음에 난이도가 별 1개짜리라는 것이 조금 의아한 문제였다. 그래도 이 문제를 공부하면서 느낀 점이 있다면 너무도 당연한 이야기지만 문제를 접하고 어떤 자료구조를 사용할지 여러모로 검토하는 자세가 필요하다는 것이다. 문제 해설을 보기 전 까지는 우선순위 큐를 사용할 방법을 전혀 생각하지 못 했다. 표기상 낮은 난이도를 보고 아무런 대책없이 문제를 해결하려고 했던 것이 문제였다. 그래도 몇 번 문제를 곱씹어 보니 어렴풋이라도 해결 방안에 대한 감을 잡을 수 있었던 것 같다.

  최근에 자기소개서 + ncs 공부로 알고리즘은 뒷전이었다. 지원 결과가 잘 되었으면 좋은 소식을 포스팅을 했을 거 같은데 그렇지 못해서 눈물을 머금고 다시 공부를 시작하게 되었다. 추후에는 아마 여러가지 진로를 고민하고 여러 방면으로 준비 + 아르바이트 등을 해야 될거 같아서 오늘처럼 중간 중간 시간이 비어있을 때 블로그를 관리하게 될 것 같다.

---

github : Algorithms/q6_0.py at main · LeeSeok-Jun/Algorithms (github.com)

LeeSeok-Jun/Algorithms