알고리즘 풀이 - 무지의 먹방 라이브

picture 22

무지의 먹방 라이브

문제 링크

문제 요약

  • 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
  • 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
  • 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.

    • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
  • 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

제한사항

  • food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
  • k 는 방송이 중단된 시간을 나타낸다.
  • 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

효율성 테스트 제한 사항

  • food_times 의 길이는 1 이상 200,000 이하이다.
  • food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
  • k는 1 이상 2 x 10^13 이하의 자연수이다.

Input

  • 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times
  • 네트워크 장애가 발생한 시간 K 초

output

  • 몇 번 음식부터 다시 섭취하면 되는지 return

해결방법

function solution(food_times, k) {
  let foods = food_times
    .map((time, idx) => {
      return { id: idx + 1, time }
    })
    .sort((a, b) => a.time - b.time)
  while (foods.length) {
    const foodCount = foods.length
    const food = foods.shift()
    if (foodCount * food.time <= k) {
      k -= foodCount * food.time
      foods = foods.map(f => {
        return { id: f.id, time: f.time - food.time }
      })
    } else {
      foods.unshift(food)
      const foodIdx = k === 0 ? 0 : k % foods.length
      const sorted = foods.sort((a, b) => a.id - b.id)
      return sorted[foodIdx].id
    }
  }
  return -1
}

시간초과가 발생한다.

효율성 테스트 제한사항을 살펴보면 k = 2 x 10^13이다.

걸리는 점

  • k를 소거 후에 모든 요소에서 소거된 k만큼 time을 삭제하고 있다.

    • 이런 행위가 시간복잡도를 늘릴 수 있다.
  • k가 저만큼 커진다면 js에서 다룰 수 있을지 모르겠다.

    • bigInt 등을 써야하려나?
    • 확인결과 Number.MAX_SAFE_INTEGER2 x 10^13보다 크다.
    • k의 값이 높아서 발생하는 문제는 없을듯하다.

해결

function solution(food_times, k) {
  let foods = food_times
    .map((time, idx) => {
      return { id: idx + 1, time }
    })
    .sort((a, b) => a.time - b.time)

  let eatAll = 0
  for (let i = 0; i < foods.length; i++) {
    const foodCount = foods.length - i
    const food = foods[i]
    if (foodCount * (food.time - eatAll) <= k) {
      k -= foodCount * (food.time - eatAll)
      eatAll = food.time
    } else {
      const foodIdx = k === 0 ? 0 : k % foodCount
      const sorted = foods.slice(i).sort((a, b) => a.id - b.id)
      return sorted[foodIdx].id
    }
  }

  return -1
}

수정사항

  • 모든 요소에 K 연산을 하던 부분을 삭제
  • foodsqueue로 다루던 것을 for문으로 변경

Written by@박대성

독서와 지식관리에 관심이 많은 개발자

GitHub