6.무지의 먹방 라이브

📍 문제 설명

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

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

 

💡 접근

처음에는 while, for문을 이용해서 풀려고 했으나 다 먹은 음식도 계속해서 체크를 하기 때문에 오답이었다.

ArrayList로 해보려 했지만 음식을 없앨 순 없어도 음식 번호를 기억하는게 불가능했다.

 

그래서 큐를 사용해보기로 했다.

음식을 먹고나서 처리를 해주었다. 정확성은 15, 30번만 제외하고 풀렸다.

왜 틀린지는 질문란과 인터넷 검색해도 잘 안나와있어서 보류..

 

-> 우선순위 큐를 이용해야만 효율성 점수를 받을 수 있는 문제라고한다.

왜 큐로는 효율성에서 탈락할까를 생각해봤다.

문제를 보면 네트워크 장애가 발생하는 k초는 최대 2 x 10^13 만큼의 시간을 갖는다.

1초씩 작업을 해주는 큐는 2 x 10^13번 만큼의 연산을 해줘야 된다는 의미

 

그러면 일단 제일 음식이 적은 것부터 한꺼번에 빼준다면

즉 K가 15초이고 음식이 8, 6, 4초라면

처음에 우선 순위 큐에서 가장 빨리 다 먹는 3번 음식(4초)을 꺼낸다.

남은 시간은 남은 음식 갯수(3) x 먹는 시간(4) 이다. K = 3

다른 음식(8초,6초)에 대한 연산을 하지 않는 이유는 음식의 번호를 찾는것이 목적이기 때문이다.

남은시간은 3초이고 13초 8 14초 6 15초 8 을 먹고 다음에는 6을 먹게 된다.

 

이론은 이해가 됐는데 코드는 넘 복잡하다. 다음에 다시 풀어보자..!!

 

제일 섭취시간이 짧은 것 부터 계산

now = pq.poll().getTime() - 4

summary = (now - previous) * length - (4 - 0) * 3 = 12

4초 걸리는 음식을 한번에 다 먹은거다. - 총 12초 소요

 

남은 음식 제외

length -= 1 = 2;

previous = now = 4 //이전 음식 시간 재설정

 

6초 걸리는 음식을 한번에 다 먹으려면 16초가 소요되는데 15초에서 네트워크 장애가 일어난다.

summary + ((pq.peek.getTime() - previous) * length) > 15임

따라서 한번에 다 먹을 수 없고 남은 음식은 따로 리스트에 넣어둔다.

[(1,8), (2,6)]

 

여기서는 시간이 아닌 음식번호를 기준으로 정렬시키고

네트워크 장애 시간인 k 와 먹기위해 사용한 시간인 summary를 빼준다. - 3

그리고 length로 나누어주면 먹어야할 음식 번호가 나온다.

 

 

👩‍💻 코드

1.while안에 for문 이용(매우 비효율적)

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int[] food_times = {3,1,2};
        long k = 5;

        //경과시간 체크
        int sec = 0;
        //해당 음식번호 체크
        int num = 0;

        while(true) {
            for(int i = 0; i < food_times.length; i++) {
                //음식이 있으면 음식을 먹는다
                if(food_times[i] != 0) {
                    sec++;
                    food_times[i]--;
                    num = i;
                }
            }
            if(sec == k) break;
        }
        //끝음식이라면 첫번째 음식 먹을차례
        if(num == food_times.length - 1) num = 1;
        else num += 1;
        System.out.println(num);

    }
}

 

2.큐를 이용하여 남아있는 음식들만 연산(정확성 90%)

import java.util.*;

class Food {
    public int FoodNumber;
    public int FoodCapacity;

    public Food(int FoodNumber, int FoodCapacity){
        this.FoodNumber = FoodNumber;
        this.FoodCapacity = FoodCapacity;
    }

    @Override
    public String toString() {
        return "Food{" +
                "FoodNumber=" + FoodNumber +
                ", FoodCapacity=" + FoodCapacity +
                '}';
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int[] food_times = {3,1,2};
        int k = 5;

        Queue<Food> q = new LinkedList<>();
        for(int i = 0; i < food_times.length; i++) {
            q.offer(new Food(i+1, food_times[i]));
        }

        //먹는 시간
        long eattingTime = 0;
        //다시 먹기 시작해야하는 음식 번호
        int answer = -1;

        //(1,3) (2,1) (3,2) 가 들어갔음
        //음식을 꺼내서 하나씩 먹고 다 먹었으면 뺀 상태 그대로 유지시킨다.
        //다 안먹었으면 다시 넣어준다.
        while(!q.isEmpty()) {
            System.out.println(q);
            //첫번째 음식을 꺼낸다
            Food food = q.poll();
            //먹는다.
            int nowFoodCapacity = food.FoodCapacity -1;
            //먹었으면 1초 경과
            eattingTime++;

            //먹고나서 다른 음식들이 없다면 끝내기
            if(q.size() == 0) break;

            //먹고나서 네트워크 장애가 발생했으면 다음 음식의 번호를 저장
            if(eattingTime == k) {
                answer = q.peek().FoodNumber;
                break;
            }

            //먹고 나서 지금 현재 음식이 남아있으면 큐에 다시 넣어주기
            if(nowFoodCapacity != 0) {
                q.offer(new Food(food.FoodNumber, nowFoodCapacity));
            }
        }

        System.out.println(answer);

    }
}

 

3.우선순위 큐 이용하여 한꺼번에 연산

import java.util.*;

class Food implements Comparable<Food> {

    private int time;
    private int index;

    public Food(int time, int index) {
        this.time = time;
        this.index = index;
    }

    public int getTime() {
        return this.time;
    }

    public int getIndex() {
        return this.index;
    }

    // 시간이 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Food other) {
        return Integer.compare(this.time, other.time);
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        // 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
        long summary = 0;
        for (int i = 0; i < food_times.length; i++) {
            summary += food_times[i];
        }
        if (summary <= k) return -1;

        // 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
        PriorityQueue<Food> pq = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            // (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
            pq.offer(new Food(food_times[i], i + 1));
        }

        summary = 0; // 먹기 위해 사용한 시간
        long previous = 0; // 직전에 다 먹은 음식 시간
        long length = food_times.length; // 남은 음식의 개수

        // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
        while (summary + ((pq.peek().getTime() - previous) * length) <= k) {
            int now = pq.poll().getTime();
            summary += (now - previous) * length;
            length -= 1; // 다 먹은 음식 제외
            previous = now; // 이전 음식 시간 재설정
        }

        // 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
        ArrayList<Food> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        // 음식의 번호 기준으로 정렬
        Collections.sort(result, new Comparator<Food>() { 
            @Override
            public int compare(Food a, Food b) {
                return Integer.compare(a.getIndex(), b.getIndex());
            }
        });
        return result.get((int) ((k - summary) % length)).getIndex();
    }
}