알고리즘 풀이 - 무지의 먹방 라이브
January 09, 2021
무지의 먹방 라이브
문제 요약
- 무지는 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
}수정사항
- 모든 요소에
K연산을 하던 부분을 삭제 foods를queue로 다루던 것을for문으로 변경
