[JAVA] 프로그래머스 LEVEL3 [1차] 셔틀버스

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

프로그래머스

코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > [1차] 셔틀버스

 

난이도: LEVEL3

알고리즘 유형:  그리디?

풀이 설명 

1. 우선순위 큐에 크루들 도착 시간 순서대로 넣기 

PriorityQueue<Integer> pq = new PriorityQueue<>();
for(String next : timetable){
    String [] split = next.split(":");
    int sum = 0;
    sum += Integer.parseInt(split[0]) * 60;
    sum += Integer.parseInt(split[1]);
    pq.add(sum);
}

 

2. 버스 도착 시간 구해서 순서대로 큐에 넣기 

Queue<Integer> bus = new LinkedList<>();
public static void addBus(int n, int t, Queue<Integer> bus){
    int start = 60 * 9; // 9시 
    while(n --> 0){
        bus.add(start);
        start += t;
    }
}

 

3. 핵심 로직 

ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int size = bus.size();
int[] memo = new int [n];
int index = 0;
while(size --> 0){
    int cur = bus.poll(); // 버스 도착 시간 
    ArrayList<Integer> temp = new ArrayList<>();
    while(temp.size() < m && !pq.isEmpty() && pq.peek() <= cur){
        temp.add(pq.poll());
    }
    list.add(temp);
    memo[index++] = cur;
}

이중 리스트에 해당 시간에 버스 타는게 가능한 각 크루들 도착 시간 넣기 

 

4. 콘의 시간 구하기 

int answer = 0;
ArrayList<Integer> temp = list.get(list.size() - 1);
System.out.println(temp);
if(temp.size() == m){ // 마지막 버스의 자리가 없다면? 
   int last = temp.get(m - 1); 
   answer = last - 1; 
} // 마지막 버스에 자리가 있으면 마지막 버스 도착 시간 
else answer = memo[n - 1];

 

콘이 셔틀을 타고 사무실로 갈 수 있는 가장 늦은 도착 시간을 구한다.

버스에 자리가 없다고 하면 마지막 버스의 마지막 탑승자 보다 1분 먼저 도착하기 

마지막 버스에 자리가 있으면 마지막 버스 도착 시간이 가장 늦은 시간이다. 

 

5. 구한 시간 문자열로 바꾸기 

return makeAnswer(answer);

public static String makeAnswer(int time){
    StringBuilder sb = new StringBuilder();

    int hour = time / 60;
    int min  = time % 60;

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

    sb.append(":");

    if(min < 10){
        sb.append(0).append(min);
    }
    else sb.append(min);

    return sb.toString();
}

 

정답 코드 

import java.util.*;
class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(String next : timetable){
            String [] split = next.split(":");
            int sum = 0;
            sum += Integer.parseInt(split[0]) * 60;
            sum += Integer.parseInt(split[1]);
            pq.add(sum);
        }
        Queue<Integer> bus = new LinkedList<>();
        addBus(n, t, bus);
        
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int size = bus.size();
        int[] memo = new int [n];
        int index = 0;
        while(size --> 0){
            int cur = bus.poll(); // 버스 도착 시간 
            ArrayList<Integer> temp = new ArrayList<>();
            while(temp.size() < m && !pq.isEmpty() && pq.peek() <= cur){
                temp.add(pq.poll());
            }
            list.add(temp);
            memo[index++] = cur;
        }
        
        int answer = 0;
        ArrayList<Integer> temp = list.get(list.size() - 1);
        System.out.println(temp);
        if(temp.size() == m){ // 마지막 버스의 자리가 없다면? 
           int last = temp.get(m - 1); 
           answer = last - 1; 
        } // 마지막 버스에 자리가 있으면 마지막 버스 도착 시간 
        else answer = memo[n - 1];
        
        return makeAnswer(answer);
    }
    public static String makeAnswer(int time){
        StringBuilder sb = new StringBuilder();
        
        int hour = time / 60;
        int min  = time % 60;
        
        if(hour < 10){
            sb.append(0).append(hour);
        }
        else sb.append(hour);
        
        sb.append(":");
        
        if(min < 10){
            sb.append(0).append(min);
        }
        else sb.append(min);
        
        return sb.toString();
    }
    public static void addBus(int n, int t, Queue<Integer> bus){
        int start = 60 * 9; // 9시 
        while(n --> 0){
            bus.add(start);
            start += t;
        }
    }
}