[프로그래머스] 무지의 먹방 라이브

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
  • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

이 문제를 일반적으로 생각해보자.

총 3가지 음식이 있다고 가정하자. 그러면 첫번째 부터 이동하게 된다.

그리고 1초뒤 다른 음식을 먹게 된다.

이것을 어디까지 하냐가 문제인데... 모든 음식을 다먹거나 네트워크 장애가 발생할때 까지 하면 된다.

그러면 시간 변수 time를 만들어 두고

그것을 계속해서 증가시킨다. 그런데 만약 맨 마지막 음식을 갔음에도 불구하고 k초가 지나지 않는다면

다시 i를 0으로 이동시켜줘야한다.

근데 문제는 음식의 총 갯수는 200,000개이며

음식의 크기는 100,000,000가 된다 이말이 무슨 말이냐면

반복문 하나가지고는 불가능하다는 이야기다. 답이야 맞출 수 있을 지 모르겠지만...

확실한건 시간초과가 날것이 뻔하다.

그러면 다른 방법을 찾아야 한다.

고민을 해보자.

각각의 음식은 크기를 가진다. 어떤 것은 1, 또 어떤 것은 3이 등장한다.

값이 작다는 의미는 이 음식의 섭취속도가 가장 빠르다는 것을 의미한다.

물론, 음식의 크기가 1인 음식이 중간일 경우에는 그 전음식을 섭취해야 되지만 말이다.

 

이를 활용해야 할것 같다.

그러면 이런식이 나온다.

while ( sum + (pq.peek().time - previous) * len <= k) {
            long now = pq.poll().time;
            sum += (now - previous) * len;
            len--;
            previous = now;
}

 우리가 주목해야하는 부분은 바로 sum이랑 (pq.peek().time - previous) * len 부분이다.

그 전에

예제를 살펴보자.

각 음식은 [3, 1, 2] 가진다고 하자.

그러면 누가 봐도 2번 음식이 가장 먼저 섭취하게 된다. 

다시 작성해보자

[(1,2),(2,3),(3,1)] 이런식으로 2번 음식이 가장 먼저 섭취가 완료된다는 것을 알 수 있다.

그러면 2번이 섭취가 완료 되었을때 3번은 어떨까?

3번은 섭취가 안된 상태로 진행이 될것이다. 하지만 1번은 섭취하였기 때문에 3이 아닌 2가 저장이 된다.
결국은 섭취가 되지만 말이다.

자 다시 위 식을 다시 들어가보자

위 식에서 새로 정의된 부분은 전부 값은 0이다.

그렇기 때문에  0 + (1- 0) * 3 이 된다.

값은 3이 된다. 

이건 모든 음식을 섭취했다는 뜻이 된다.

그러면 다음은 어떻게 될까?

바로 5가 된다. 5는 3에서 2를 더한 값이다 즉, 아직까지도 모든 음식 섭취가 가능하다.

다음은 6이 되기 때문에 모든 음식 섭취가 불가능하다.

 

즉 

while ( sum + (pq.peek().time - previous) * len <= k) {
            long now = pq.poll().time;
            sum += (now - previous) * len;
            len--;
            previous = now;
}

 

이 식은 전해진 배열을 순회하면서 무언가를 소비할때 사용되는 코드라고 볼 수 있다.

마지막으로

foods.get((int)((k-sum)%len)).index;

이 코드를 알아야 하는데..

k - sum의 값은 뭘까?

k = 5 sum = 5 즉 여기에서는 0이 된다. len은 1기 때문에 여기서는 무조건 1이지만 생각을 해보자.

과연 k와sum이 같아야할 필요가 있을까?

그럴일은 생각은 나지않지만... 이뜻은 무조건 첫번째가 아닐 수 있다는 뜻이 아닐까 라는 생각을 하게 된다... 이부분은 조금만더 생각해보자...ㅜㅜ