알고리즘(셔틀버스, 무지의 먹방 라이브)

[셔틀 버스]

 

* 로직

• 시간을 분으로 변환하여 우선순위 큐에 저장한다
• 우선순위 큐는 시간 기준 오름차순 정렬이다
• 마지막 운행 횟수 전까지는 대기열에 있는 인원들을 출발시킨다
• 마지막 운행 시점에서 m-1명을 태운 뒤 콘의 탑승 가능 시간을 정한다
  • 큐가 비어있다면 => 마지막 셔틀의 출발시간에 탑승 가능하다
  • 큐가 비어있지 않다면
    • 제일 빠른 대기열 시간 > 마지막 셔틀의 출발시간 => 마지막 셔틀의 출발시간에 탑승 가능하다
    • 제일 빠른 대기열 시간 <= 마지막 셔틀의 출발시간 => 제일 빠른 대기열 시간 - 1 시간에 탑승 가능하다
• 탑승 가능한 값을 다시 시간 형태로 변환한다

 

//셔틀 버스(17678)
import java.util.Comparator;
import java.util.PriorityQueue;

public class Problem_ShuttleBus {

    public static void main(String[] args) {
        int n = 1;
        int t = 1;
        int m = 5;
        String[] timetable = {
                "08:00", "08:01", "08:02", "08:03:"
        };

        String answer = solution(n, t, m, timetable);
        System.out.println(answer);
    }

    public static String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        //convert time
        for(String input : timetable){
            String[] time = input.split(":");
            int hour = Integer.parseInt(time[0]);
            int minute = Integer.parseInt(time[1]);
            int convertedTime = (hour *60) + minute;

            priorityQueue.offer(convertedTime);
        }

        //마지막 운행횟수 전까지는 대기열 인원들 출발
        int shuttle = 9;
        int startTime;
        int cnt;
        for(int i=0; i<n-1; ++i){
            startTime = (shuttle * 60) + (i * t);
            cnt=1;

            while (!priorityQueue.isEmpty() && cnt <= m){
                Integer q = priorityQueue.poll();
                if(q <= startTime){
                    cnt++;
                }
                else {
                    priorityQueue.offer(q);
                    break;
                }
            }
        }

        //마지막 운행을 기준으로 비교
        startTime = (shuttle*60) + (n-1)*t;
        cnt=1;
        while (!priorityQueue.isEmpty() && cnt < m){
            Integer q = priorityQueue.poll();
            if(q <= startTime){
                cnt++;
            }
            else {
                priorityQueue.offer(q);
                break;
            }
        }

		int possibleTime = 0;
        if(priorityQueue.isEmpty()){
            possibleTime = startTime;
        }
        else {
            if(priorityQueue.peek() > startTime) possibleTime = startTime;
            else possibleTime = (priorityQueue.peek() - 1);
        }

        //convert time to string
        int hour = possibleTime / 60;
        int minute = possibleTime % 60;
        StringBuilder sb = new StringBuilder();

        //hour
        if(hour < 10){
            sb.append("0");
            sb.append(hour);
        }
        else sb.append(hour);

        sb.append(":");

        //minute
        if(minute < 10){
            sb.append("0");
            sb.append(minute);
        }
        else sb.append(minute);

        return answer = sb.toString();
    }
}

 

 

[무지의 먹방 라이브]

 

* 로직

• k / 원소 개수(size)는 사이클을 돌릴 때 처리되는 값이 되고, 나머지는 이후 몇 번째 음식까지 갈 수 있다는 원리를 이용한다
• 우선 기존의 음식 정보들을 큐에 담는다
• 여기서 핵심은 매 원소마다 1씩 감소시키는게 아니라 한번에 처리하는게 중요하다(효율성 문제)
• 현재 큐에 존재하는 원소들을 기준으로 사이클을 돌때 처리되는 값(k/size)을 각각 원소에서 빼준다
• 이때, 해당 음식의 양이 0 이하가 된다면 사이클을 도는 동안 카운팅이 되어서는 안된다
  
  • 즉, 카운팅되지 말아야할 횟수를 누적시키고 해당 시간만큼 늘려놓으면 된다
• 위 로직이 끝났다면
  • 큐가 비었다면 => -1을 리턴
  • 비어있지 않고
    • k>0이라면 => k==0이 되는 곳의 index를 출력한다
    • k<=0이라면 => 큐의 첫번째 원소 index를 출력한다

 

import java.util.LinkedList;
import java.util.Queue;

class FoodInfo{
    public int idx;
    public int amount;

    public FoodInfo(int idx, int amount) {
        this.idx = idx;
        this.amount = amount;
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        int answer = 0;
        Queue<FoodInfo> queue = new LinkedList<>();
        for(int i=0; i<food_times.length; ++i){
            queue.offer(new FoodInfo(i+1, food_times[i]));
        }

        //사이클을 돌릴 수 있을 때까지 진행
        while (!queue.isEmpty() && k>0){
            int size = queue.size();
            long eat = k/size;
            k %= size;

            if(eat == 0) break;

            long rest=0;
            for(int s=0; s<size; ++s){
                FoodInfo q = queue.poll();
                q.amount -= eat;
                if(q.amount <= 0){
                    rest -= q.amount;
                }
                else queue.offer(q);
            }

            //해당 사이클에서 이미 음식이 없다면 그만큼 음식의 순서를 앞으로 당겨야 하기 때문에
            k += rest;
        }

        if(queue.isEmpty()) answer = -1;
        else {
            if(k > 0){
                while (!queue.isEmpty()){
                    FoodInfo q = queue.poll();
                    if(k == 0) {
                        answer = q.idx;
                        break;
                    }
                    k--;
                }
            }
            else answer = queue.peek().idx;
        }

        return answer;
    }
}