[PYTHON] 무지의 먹방 라이브 (프로그래머스 kakao 2019)

미리 스포 -> 이분탐색으로 풀어보기

 

효율성 때문에 겁부터 먹고 들어 갔다.

 

아무런 알고리즘 없이 문제에서 설명한 그대로 구현한다면 입출력 예 1번 처럼 k가 5라면 최소 5번은 확인해야한다.

 

만약 k가 2*10^13 이라면 2*10^13 번 확인해야하므로 시간초과가 난다.

 

즉, 문제 설명대로 구현하지 말고 "어떠한 아이디어를 떠올려봐라"가 핵심이다. 그래서 프로그래머스에서 lv4를 책정한듯 하다.

 

이런 문제를 접근하기 위해서 시뮬레이션 해보고 규칙이 있는 지 찾아보는 것이 우선이다.

 

규칙을 찾기 위해 그냥 문제에서 하라는 대로 해보았다.

 

먼저 아래의 표를 해석해 보자.

(참고로)

임의의 테스트 케이스 food_times = [4,2,3,6,7,1,5,8] k=16 이라고 해보자.

3(1초) 라는 말은 1초인 상황에서 food_items[0] 의 값이 4에서 1을 뺀 값이다. 즉, 1초가 딱 지났을 때 남은 음식 시간이다.

1(2초) 라는 말은 2초인 상황에서 food_items[1] 의 값이  2에서 1을 뺀 값이다. 즉 2초가 딱 지났을 때 남은 음식 시간이다.

...

 

food_items[6] 에서 1(25초)를 보자. 25초가 딱 지난 시점에 food_items 배열을 출력하면 어떻게 될까?

[0,-2,-1,2,3,-3,1,5] 가 출력된다. 마지막 food_items[7] 은 아직 먹지 않았기 때문에 21초의 값 그대로 가져온다.

 

5초가 지난 시점에 food_items를 출력하면?

[3,1,2,4,6,1,5,8]

 

8초가 지난 시점에 food_items를 출력하면?

[3,1,2,5,6,0,4,7]

 

필자가 원하는 것은 바로 8초 일때 마지막 인덱스를 가리키고, 15초 일때 마지막 인덱스를 가리키고, 21초일 때 마지막 인덱스를 가리키고,,,

 

즉 마지막 인덱스를 가리킬때 시간을 구할 수 있다면 한번 추가적인 탐색으로 끝낼 수 있을 거 같았다.

 

여기서 규칙을 하나 발견할 수 있었다.

 

모든 행에 2를 빼보자.

 

그러면 [2,0,1,4,5,-1,3,6] 이 된다. 여기서 모든 행에 2를 뺏다는 말은 배열의 길이* 2 만큼 돌았다는 뜻이다. 즉, 2바퀴 돌면 모든 행에 2씩 뺄 수 있다. 2바퀴 돌면 총 16초 일때 마지막 인덱스를 가르켜야 하지만 food_items에서 모든 음수를 더하면 즉 -1 을 더하면 15가 된다.

 

15초일때 마지막 인덱스를 가리키게 된다는 것이다.

 

하나 더 예를 들어보자.

 

모든 행에 3을 빼보자.

 

그러면 [1,-1,0,3,4,-2,2,5] 가 된다. 여기서 모든 행에 3을 뺏다고 했으니 3바퀴 돌았다는 뜻이므로 마지막 인덱스를 가리키면 8*3 인 24초 후에 마지막 인덱스를 가리키게 될것이다. 하지만 배열의 모든 음수를 더하면 (스킵한 수) 24 -1 -2 = 21초 이다. 즉, 21초 가 되면 마지막 인덱스에 도착한다.

 

모든 행에 4를 빼보자.

 

그러면 [0,-2,-1,2,3,-3,1,4] 가 된다. 여기서 4바퀴 돌았으므로 8*4 초 후에 마지막 인덱스를 가리킬 것으로 예상되지만

8*4 -2 -1 -3 초 후에 마지막 인덱스를 가리키게 된다. 즉 26초 후에 마지막 인덱스를 가리킨다.

 

핵심은 모든 행에 어떤 수를 뺄 것인가?? 이다.

 

모든 행에 빼는 수를 더할 수록 시간은 반드시 증가하므로 이분 탐색을 적용하여 모든 행에 뺄 수를 정할 수 있다.

 

예를 들어 k 가 16이라면 k보다 작거나 같은 수들 중에서 마지막 인덱스를 가리키는 최대 초 수를 이분탐색으로 구하면 된다.

16이라면 8초와 15초가 후보가 될것이며 15초가 최대 초 수에 해당 된다.

 

15초일때 마지막 인덱스를 가리킨다고 구했다면

16초일때 0번째 인덱스에 해당하는 음식을 먹을 것이고,  다음 먹을 음식의 인덱스는 2가 된다.

 

따라서 답은 2라고 하지만 문제에서 인덱스는 1부터 시작하므로 2에서 1을 더해줘야 한다.

 

 

코드의 가독성이 좋진 못하지만, 힌트가 되었으면 좋겟다.

 

v 와 idx 는 마지막 인덱스를 가리킬때의 시간(초) 를 나타낸다.

cutting 은 모든 행에 얼마를 빼야할지 정하는 수다.

n 은 배열의 길이다.