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

https://school.programmers.co.kr/learn/courses/30/lessons/42891

문제

프로그래머스

시간이 주어졌을때 무지가 다음에 먹을 음식 번호를 리턴  

풀이

푸는 방법은 알았는데 효율성 2에서 틀린 문제. 

효율성 테스트 제한 사항

• food_times 의 길이는 1 이상 200,000 이하이다.
• food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k는 1 이상 2 x 10^13 이하의 자연수이다

k 가 long 형으로 잡혀있다. 자바에서 int 의 최대 크기는 2147483647 으로 2^31 -1 이다.  파이썬에선  type inference 를 해주어 int long 신경을 안 써도 돼지만, 코테를 풀다보면 자바에서는 이번 문제와 같이 대충 2 * (10^10) 이상이면 long 타입을 써야 통과가 되는 문제들이 있다.  int, long 타입을 신경 안쓰고 풀면 효율성 2번에서 걸리게 된다.. 

 

풀이 알고리즘은 다음과 같다. 

1. 배열 길이가 200,000 임으로 브루트 포스는 절대 안된다. (제곱하면 1억 보다 훨신 큼 ) 
2. 빨리 음식 먹는 순으로 정렬한다.
2.  먹는 시간이 작은 태스크 sT [ i ] 가 종료되는 총 소요 시간  패턴을 찾는다.
3. 답을 리턴한다

 

 시간 패턴을 찾는게 이번 문제의 pov  어떻게 찾을 건데? 

 

우선 음식 먹는데 걸린 시간 배열을 정렬한 sortedTime, sT배열을 만든다.

sT[0] = 0  으로 초기화 하고 ( 뒤에서 설명 ) 

sT[1] = ( 음식 먹는데 적게 걸린 시간 ) 으로 초기화 하였다. 그 다음 배열 순회 하면서 음식을 1초씩 시식 함으로 

rest (남은 시간 ) = food_times.length 으로 초기화 한다.

 

그러면 1번째 음식을 먹는데 총 걸리는 시간 = 1번째 음식 먹는 시간 x ( 남은 음식 길이 ) rest  

time = sT[1] * rest 가 된다.

만약  time이 k( 네트워크 장애 시간까지 남은 시간 ) 보다 작으면 2번째 음식 먹는데 걸리는 총 시간을 구하면 되고, 

time > k 이면 현재 음식을 다 먹기 전에 네트워크 장애가 나온다는 뜻이다.

 

현재 음식 sT [ i ] 을 먹을때 네트워크 장애가 걸린다면, 이제 O( N ) 으로 배열 탐색을 해서 구해주면 된다. 

k %= rest 를 해주는 이유는 k 가  rest( 현재 남은 음식 길이 ) 보다 길면 모듈로를 해줘서 탐색 최적화를 하기 위함이다.

 

k 번째를 찾았으면, 답을 리턴하면 끝이다.

 

한편, 1번째가 아닌 N ( N > 1 ) 번째 음식을 먹을때는 sT [ N ] - sT [ N - 1 ] 을 해준다. N번째 음식을 먹을 차례에는, sT[n-1] 초만큼 이미 먹었기 때문이다. 따라서 sT[0] = 0 으로 dummy node 를 추가해주어 점화식이 가능하게 한다.

코드

import java.util.*;
class Solution {
    public int solution(int[] food_times, long k) {
      ArrayList<Integer> sT = new ArrayList<>();
		//주의 맨앞에 0이 있어야한다. 
		sT.add(0);
		for(int x:food_times)
			sT.add(x);
		Collections.sort(sT);
		int rest = food_times.length;
		int ans =-1 ;
		
		for(int i = 1 ;i < sT.size() ;i++) {
			long time = (long) (sT.get(i)-sT.get(i-1)) * rest;//현재 먹방까지 총 소요시간.
			if(time > k) {
				k = k % rest; //rest 는 나머지 음식 길이 
				int cnt = 0 ;
				for(int j = 0 ;j < food_times.length ;j++) {
					if(food_times[j] < sT.get(i) )continue;//다 먹었음
					if(cnt == k ) {
						ans = j+1;//k초까지 먹고난 다음 next음식
						break;
					}
					cnt++;
				}
				break;
			}
			k -= time;
			rest--;
		}
        return ans;
    }
}