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

문제 요약

food_times 배열이 주어지고 k라는 특정 시간이 주어질 때 무지가 food_times를 순차적으로 순회하며 음식을 먹을 때, k초에 먹을 예정인 음식의 index는?

첫번째 접근

• 시간과 공간 효율성을 요구하는 문제이다.

• food_times에서 값이 0인 요소는 무시해야한다는 점과 순차적 탐색을 하면 안된다는 점이 LinkedList 개념을 떠올리게 했다.

• LinkedList를 20만 크기의 배열로 만드는 것은 비효율적이라고 생각해서 TreeMap을 이용하고자 했다.

• Map을 통해 LinkedList처럼 순회하는 것은 이전에 풀었던 서로소 집합 문제와 유사하다고 생각했다.

• 그래서 프로그래머스-호텔 방 배정과 유사하게 풀이했다.

결과

• 정답율 2%

두번째 접근

• 해당 문제의 핵심은 '가장 먼저 처리되야할 것을 빠르게 꺼내는 것'이다.

• 이 대목에서 PriorityQueue를 구상할 수 있다.

• [시간, 음식의 Index]로 객체를 생성하고 시간순으로 정렬한다.

• K의 크기가 10^13이기 때문에 현재 위치에서 가장 작은 시간을 가진 위치로 가는데 걸리는 시간을 빠르게 계산해야한다.

  time = (now - prev) * len // len은 0이 아닌 요소들의 수

• pq가 빌때까지 수행하되 len이 k보다 작으면 k%len에 해당하는 index를 리턴하면 그것이 정답이다.

결과

• 정답율 100%

후기

• 프로그래머스-호텔 방 배정을 풀때의 후기와 같은 심정이다. 최적화를 위한 요소들은 많지만, 가장 처음에 생각난 것에 매몰되어서 넓게 생각하지 못했다. 다음부터는 가능성있는 자료구조와 알고리즘을 종이에 먼저 쓰고 접근 방안을 고려해야겠다.