https://programmers.co.kr/learn/courses/30/lessons/42891
-
flow
단순히 생각해봤을 때, 음식 번호 순서대로 하나씩 세면서 진행했을 때, k번째 음식을 찾으면 된다. 이를 어떻게 효율적으로 풀어볼까 고민했는데 다른 특별한 method들은 생각이 나지 않았고, 단순히 연산을 줄여보자고 생각을 했다.
섭취할 수 있는 음식의 종류를 n이라고 했을 때(초기 n은 N과 같을 것이다.), 각 음식마다 k//n 만큼 한 번에 많이 섭취한다고 생각해본다. 그에 따라 음식 남은 양도 계산해주고, k//n보다 남은 양이 적었던 음식이 있는 경우, 단순히 남아 있던 양을 0으로 만들어 주고 그만큼만 k에서 빼면 된다.(어차피 다 먹은 음식을 제외하고도 남아있는 다른 음식들 먹는 순서방향에는 변함이 없기 때문, 그리고 추가적으로 n에서 -1 해줘야함.)
위와 같은 방법으로 k가 0이 될때까지 진행했을 때, 음식의 번호가 정답이 될 것이고, 시간 복잡도는 O(NlogN)이 될 것이다. N(~=n) 가지의 음식을 k가 n보다 작아질 때까지 체크하므로 최악일때 k가 n보다 작아지기 까지 높이가 logN. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A42891.py
