무지의 먹방 라이브

CCKN·2020년 12월 26일

코딩테스트

목록 보기

23/24

무지의 먹방 라이브

문제 링크

문제 요약

무지는 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_INTEGER는 2 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
}