프로그래머스 lv3 - 셔틀버스 (자바) [2018 KAKAO BLIND RECRUITMENT]

문제

---

프로그래머스 lv3 - 셔틀버스

풀이

---

• 크루 대기열을 시간순으로 정렬한다.
• 버스가 도착할 때마다 탈 수 있는 크루원을 순차적으로 태운다.
• 순차적으로 태우다가 버스에 태울 수 있는 최대 인원이 되었을 경우 태우는 것을 종료하고 다음 버스 순서로 간다.
• 버스가 운행을 종료한 후 태운 사람 수가 버스 최대 인원보다 적으면 마지막 버스의 도착 시간이 답이다.
• 버스가 운행을 종료한 후 태운 사람 수가 버스 최대 인원만큼 찼다면 마지막 탄 크루원 시간보다 1분 앞이 답이다.

어려웠던 점

---

• 버스에 순차적으로 크루원을 태우는 로직을 가독성이 좋게 짜는 방법을 고민하는 데 시간이 좀 걸렸다.
• 버스를 다 태운 후 콘이 타야 할 시간을 체크하는 방법이 예외 케이스가 있는지 생각하느라 시간이 좀 걸렸다.

코드

---

< 내 코드 >

import java.util.*;
class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        int[] time_table = new int[timetable.length]; // timetable을 분으로 계산
        for (int i = 0; i < timetable.length; i++) {
            String[] s = timetable[i].split(":");
            time_table[i] = Integer.parseInt(s[0]) * 60 + Integer.parseInt(s[1]);
        }
        Arrays.sort(time_table);

        int time = 540; // 09:00 - 셔틀 첫 도착 시간
        int ret = 0, index = 0, person = 0;
        for (int i = 0; i < n; i++) {
            person = 0;
            for (int j = index; j < time_table.length; j++) {
                if (time >= time_table[j]) {
                    person++;
                    index++;
                    if (person == m)
                        break;
                }
            }
            time += t;
        }

        if (person < m) {
            ret = time - t;
        } else {
            ret = time_table[index - 1] - 1;
        }

        String hour = String.valueOf(ret / 60);
        String minute = String.valueOf(ret % 60);

        if (hour.length() == 1) hour = "0" + hour;
        if (minute.length() == 1) minute = "0" + minute;

        return hour + ":" + minute;
    }
}

< 더 효율적인 코드 >

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(String table : timetable) {
            int time = Integer.parseInt(table.substring(0, 2)) * 60 + Integer.parseInt(table.substring(3));
            pq.add(time);
        }

        int start_time = 9 * 60;
        int last_time = 0;
        int total = 0;
        for(int i = 0; i < n; i++) {
            total = 0;    
            while(!pq.isEmpty()) {
                int current_time = pq.peek();
                if(current_time <= start_time && total < m) {
                    pq.poll();
                    total++;
                } else break;
                last_time = current_time - 1;
            }
            start_time += t;
        }
        if(total < m) last_time = start_time - t;

        String hour = String.format("%02d", last_time / 60);
        String minute = String.format("%02d", last_time % 60);
        return hour + ":" + minute;
    }
}

참고

---

더 효율적인 코드가 있는지 확인해보기 위해 찾아보니 우선순위 큐를 활용한 깔끔한 코드가 있어서 추가로 저장해놓았다.
참고 링크 : https://moonsbeen.tistory.com/372