[2019 KAKAO BLIND RECRUITMENT] 무지의 먹방 라이브(Java)

## 접근

---

1. HashMap을 이용해서, 인덱스와 음식을 먹는데 소요되는 시간을 추가한다. 음식을 먹는데 소요되는 시간이 낮은 것부터 정렬한다.

 

 

 

2. 정렬된 키를 이용해서, 순차적으로 접근하며 k를 차감시킨다. k를 차감시킬 때, 식을 정확하게 세워야 한다. 또한, 다음 계산을 위해서 HashMap의 값들을 일일이 차감시키는 방식이 아니다. 계산이 이루어질때, 이전 가장 작은 값을 이용해서 k를 차감시킨다.

* k = k - (남아있는 개수) * (현재 가장 작은 값 - 이전 가장 작은 값)

 

 

 

3. 만약, 차감 후에 값이 음수가 나온다면, 현재 존재하는 키들의 개수를 이용해서 순서를 찾으면 된다.

 

 

 

 

## 유의사항

---

1. Long의 형태이므로, 중간 과정에서 int로 값이 변환되지 않도록 주의해서 작성한다.(효율성 2번)

 

 

 

 

 

## 해설코드

---

import java.util.*;
import java.io.*;
import java.lang.*;
 
class Solution {
    public int solution(int[] food_times, long k) {
        int answer = 0;
        int removeCnt = 0;
        int i = 0;
        
        Map<Integer, Long> hm = new HashMap<Integer, Long>();
        for(i = 0; i < food_times.length; i++)
            hm.put(i + 1, (long)food_times[i]);
        
        List<Integer> kList = new ArrayList<>(hm.keySet());
        Collections.sort(kList, (o1, o2) -> (hm.get(o1).compareTo(hm.get(o2))));
        
        boolean[] chk = new boolean[food_times.length + 1];
        
        for(i = 0; i < kList.size(); i++){
            int cnt = 0;
            long fVal = hm.get(kList.get(i));
            long preVal = 0;
            if(i != 0) preVal = hm.get(kList.get(i - 1));
            
            if(k - (long)(kList.size() - i) * (fVal - preVal) >= 0){
                k = k - (long)(kList.size() - i) * (fVal - preVal);
                
                for(int j = i; j < kList.size(); j++){
                    if(hm.get(kList.get(i)) == hm.get(kList.get(j))){
                        cnt += 1;
                        removeCnt += 1;
                        chk[kList.get(j)] = true;
                    }
                    else 
                        break;
                }
            }else
                break;
            
            i = i + (cnt - 1);
        }
        
        if(removeCnt == food_times.length) return -1;
        
        long tmp = k % (kList.size() - removeCnt) + 1;
        for(int j = 0; j < food_times.length; j++){
            if(!chk[j + 1]) 
                tmp -= 1;
 
            if(tmp == 0){
                answer = j + 1;
                break;
            }
        }
        
        return answer;
    }
}