[프로그래머스] 2019 카카오 블라인드 #4 무지의 먹방 라이브 (Java)

#4 무지의 먹방 라이브

난이도 : LEVEL 4

유형 : 자료구조

코딩테스트 연습 - 무지의 먹방 라이브

▸ 문제

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

 

 

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

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

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

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

▸ 제한사항

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
• k 는 방송이 중단된 시간을 나타낸다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

▸ 정확성 테스트 제한 사항

• food_times 의 길이는 1 이상 2,000 이하이다.
• food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
• k는 1 이상 2,000,000 이하의 자연수이다.

▸  효율성 테스트 제한 사항

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

 

문제 풀이  

이런 유형은 처음 접해봤다. 어떻게보면 매일 DP, 그래프, 트리와 같은 틀이 정해져있는 문제만 풀다가 이렇게 수학적(?)인 문제를 푸니깐 신선하고 재밌었다. 결국 못풀었지만 말이다. 경험이 없다보니 효율성 테스트까지 고려해서 생각하면 설계가 몹시 어려웠다. 개인적으로는 이게 2019년도 카카오 코테 중 가장 어려운 문제같다.

 

k를 최대한 줄이는 방향으로 가는 것까지 잡고 데이터를 정렬해서 남은 k로 남은 음식들을 카운트해주는 것 까지도 어거지로 구현했는데 시간초과가 발생하였다. 아이디어는 맞았지만 쓸데없는 연산이 너무 많고 여러 엣지 케이스를 통과하지 못했다. 결국 해설을 참고하였다.

 

구상

프로그램 자체는 간단하다. 1초에 음식 1개씩 먹고 주어진 k초에 어떤 음식을 먹을 차례인지 출력해주면 된다. 문제는 효율성인데 20만개의 음식 종류, 각 음식 마다 1억개를 가지고 있으므로 최악의 경우 20만 * 1억번의 반복문이 실행된다.

 

해결책은 k를 비선형 구조로 줄여나가는 것이다. dp, 이진탐색, 파라메트릭 등등 뭐 생각나는 거 다 껴넣어봤지만 관통하는 알고리즘은 없었다.(적어도 내 머릿속에서는...) 그러므로 이 문제에만 해당하는 새로운 규칙을 만들어야했다.

 

규칙 찾기

1번 음식부터 ~ n번 음식까지 도는 것을 한 싸이클이라고 한다면 해당 싸이클의 주기는 특정 지점마다 변경된다. 그 지점은 현재 있는 음식 종류 중 가장 적은 양을 지닌 음식이 0이 될 때이다. 음식이 없으면 해당 구간은 건너뛰므로 주기가 짧아지게된다.

 

이 싸이클의 종료 시점인 k는 계속 변하는 주기에 따라 줄어드는 거리도 다를 것이며 그 거리는 주기*싸이클 길이(가장 적은 음식 양 * 음식 종류의 갯수)가 된다. 변동하는 속도에 따라 k값을 감소시켜주고 더 이상 줄어들지 않을 때 해당 구간을 탐색하여 빠르게 값을 찾아낼 수 있다.

 

k=13, [ 2, 3, 5, 4 ]의 데이터로 예를 들어보자.

 

음식의 양에 따라 오름차순으로 데이터를 정렬한 후 싸이클에 따라 구분지으면 다음과 같다.

 

[2 3 5 4]

이렇게 되면 한 싸이클당 움직이는 거리를 확연히 알아 볼 수 있다. 1번 싸이클은 8, 2번은 3, 3번은 2, 4번은 1이다. k=13은 3번 싸이클 구간에 속하게 된다. 3번 싸이클의 시작은 12부터이고 남은 음식은 [5 4]이기 때문에 해당 구간에서 2번째 순서에 해당하는 4번 음식이 정답이다. 여기서 주의해야 할 점은 구간 안에서 정렬된 순서로 음식을 고르면 안되고 기존에 주어진 순서로 고려해서 선택해줘야 한다.

 

설계

규칙을 찾아도 구현을 못하면 말짱 도루묵이다. 어떠한 자료구조를 선택하고 데이터를 어떻게 처리할 것인지 정하는 것도 중요하다.

1. 각 음식을 양에 따라 오름차순으로 정렬한다.
2. 정렬된 데이터를 순차적으로 탐색하여 k가 해당하는 구간을 찾아준다.
   1. 이번에 먹을 음식의 양(sub)을 계산해준다. (현재 싸이클에서 가장 적은 음식 양 - 이전에 먹은 음식 양) sub = food_times[fIdx] - prev;
   2. sub >0 , 아직 먹을 음식이 남았으므로 k가 줄어드는 속도는 tmp= sub*size(남은 음식 갯수)을 구해준다.
      1. tmp <= k, 이라면 아직 k가 속한 구간이 아니므로 k-= tmp를 해준다.
      2. tmp >k, 라면 해당 구간에 속하므로 나머지(k%size)를 구해 남은 음식 중에서 해당하는 번호를 출력해준다.

 

Collections.sort(foodList.subList(idx, food_times.length));

foodList에는 현재 각 음식의 갯수대로 정렬되어 있다. 예를 들어 [2, 3, 5, 4]였다면 List에는 [0, 1, 3, 2]로 음식의 인덱스가 저장되어있다. 그래서 마지막에는 원래 기존의 주어진 데이터 순서로 고려해줘야하기 때문에 다시 index별로 정렬해주는 것이다.

 

마지막에 사용한 로직은 나도 처음써본다.  subList는 List를 잘라서 제공해주는 것인데 메모리 누수 위험도 있다하니 무분별하게 사용하지는 말라고한다. 현재까지 다 먹은 음식은 2개이므로 subList 메소드를 사용하여 (2, n)개의 음식만을 고려할 수 있도록 했다. 그렇게 되면 남은 음식의 인덱스 [3, 2]만을 고려할 수 있게 된다.

 

사실 이렇게 안해도 현재 idx(fromIndex)를 아니 따로 메소드를 뺴주어서 해당하는 음식 idx를 뽑아주도록 설계해도 되지만 PS할 때는 나름 꿀메소드일 것 같다. 기억해둬야겠다.

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

 

 

풀이 코드 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
    static List<Integer> foodList;
    public int solution(int[] food_times, long k) {
		int answer = 0;
        int size = food_times.length;   
        foodList = new ArrayList<>();
        for(int i=0; i<size; i++) {
        	foodList.add(i);
        }
        
        Collections.sort(foodList, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return food_times[o1]-food_times[o2];
			}
		});
        
        int prev = 0;
        int idx=0;
        for(int fIdx : foodList) {
        	long sub = food_times[fIdx] - prev; // 현재 가장 적은 음식 양 - 이전에 먹은 음식 양
        	
        	if(sub>0) {
        		long tmp = sub*size; // 줄어들 음식 양 * 남은 음식 갯수
        		if(tmp <= k) {
        			k -= tmp;
        			prev = food_times[fIdx];
        		}else {
				k %= size;
        			Collections.sort(foodList.subList(idx, food_times.length));
        			return foodList.get(idx+(int)k)+1;
        		
        		}
        	}
        	idx++;
        	size--;
	}
	return -1;
    }
}