프로그래머스 [Lv. 4] 무지의 먹방 라이브 {언어 : JavaScript} [다시 풀어 보기, 힙X]

문제 링크

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

프로그래머스

정답 코드

function solution(food_times, k) {
    const n = food_times.length;
    const sortArr = food_times.map((e, idx) => [e, idx+1]);
    sortArr.sort(([a, b], [c, d]) => a - c);
    let answer = -1;
    let prev = 0;
    for (let i = 0; i < n; i++) {
        const left = n - i;
        const time = (sortArr[i][0] - prev) * left;
        if (k >= time) {
            k -= time;
            prev = sortArr[i][0];
        } else {
            const newArr = sortArr.slice(i);
            newArr.sort(([a, b], [c, d]) => b - d);
            answer = newArr[k%left][1];
            break;
        }
    }
    return answer;
}

풀이 방법

 

1. food_times 배열에 각 음식의 소모 시간과 인덱스를 결합해 2차원 배열 sortArr로 만들고, 소모 시간을 기준으로 오름차순 정렬한다.
2. prev 변수를 사용해 이전 음식의 소모 시간을 추적하며, 루프를 통해 각 음식의 남은 소모 시간을 계산한다.
3. 현재 음식 소모 시간(sortArr[i][0] - prev)과 남아있는 음식 개수로 이번 단계에서 소모할 총 시간을 구한다.
4. k가 이번 단계에서 소모할 총 시간보다 크거나 같으면, k에서 해당 시간을 빼고 prev를 업데이트하며 다음 음식으로 이동한다.
5. k가 이번 단계의 총 시간을 감당하지 못하면, 남은 음식 배열을 추출하고 인덱스를 기준으로 정렬한다.
6. 남은 음식 중에서 k % 남은 음식 개수 번째 음식을 찾아 해당 음식의 인덱스를 결과로 반환한다.
7. 루프가 끝나도 k를 소모하지 못하면 정답은 -1이 된다.
8. 결과적으로, 시간 k 이후에 먹을 음식의 인덱스를 반환하거나 더 이상 음식이 없으면 -1을 반환한다.

 

느낀점

• 문제를 풀다가 모르겠어서 검색을 해봤는데 힙을 쓰는 경우를 봤다.
• 하지만 힙을 쓸 경우 push와 pop을 모두 사용할 때 효율적이라고 봤고 다른 풀이에서는 pop만 사용했기에 새로운 풀이 방식을 간구했다.
• 어쨌든 어떻게 풀지 잘 몰랐었는데 다음에 다시 풀어보면서 이런 문제는 안틀릴 수 있도록 해야겠다.