[프로그래머스][Level3]셔틀버스 -JAVA

[문제]

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

코딩테스트 연습 - [1차] 셔틀버스

 

[풀이]

어떤 알고리즘을 알아야만 풀수 있는 문제가 아닌 문제에 주어진 상황을 코드로 구현할 수 있는지 보는 문제같다. 

 

1. 

큰 틀은 다음과 같이 구현했다. 

1) 탑승객들을 빨리 도착한 시간 순서대로 줄 세운다(PriorityQueue 사용)

2) 09:00 부터 n회 t분 간격으로 버스가 오게 한다. (for문 순회)

3) 버스 한대가 올때마다 해당 버스도착 시간까지 도착한 탑승객들을 최대 m명 태운다.

 

 2. 

이때 게으른 콘이 셔틀버스를 탑승할 수 있는 가장 늦은 시간을 구해야 한다. 

가장 늦은 시간이면 가장 늦게 오는 셔틀 버스를 타면 된다. 가장 늦게 오는 셔틀버스를 타는 경우는 2가지가 있다. 

case1) 가장 마지막 셔틀버스에 빈자리가 있는 경우
       --> 마지막 셔틀버스 도착시간에 딱맞춰 save하면 됨.

case2) 가장 마지막 셔틀버스가 만석인 경우
       --> 가장 마지막에 탑승한 승객보다 1분 먼저 도착하면 됨.

 

[코드]

package com.algorithm.kakaoTest.two;

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;

/**
 * 문제: 셔틀버스
 * 소요시간: 49분 34초
 */
public class Test03 {
    public static void main(String[] args) throws ParseException {

        int n = 1;
        int t = 1;
        int m = 1;
        String[] timetable = {"09:10", "09:09", "08:00"};

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

    public static String solution(int n, int t, int m, String[] timetable) throws ParseException {
        Date answerDate = null;
        SimpleDateFormat df = new SimpleDateFormat("HH:mm");

        PriorityQueue<Date> pq = new PriorityQueue<>();
        for (String time : timetable) {
            Date date = df.parse(time);
            pq.add(date);
        }
        
        String startTime = "09:00";
        Date date = df.parse(startTime);
        Calendar cal = Calendar.getInstance();
        cal.setTime(date);

        List<Date> bus = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            Date curTime = cal.getTime();

            bus.clear();
            while (!pq.isEmpty() && bus.size() < m) {
                Date person = pq.peek();
                if (person.getTime() <= curTime.getTime()) {
                    bus.add(pq.poll()); // 버스에 탑승, queue에서 제거
                } else {
                    break;
                }
            }

            // 현재 버스가 마지막 버스이면 
            if (i == n - 1) {
                if (bus.size() < m) { // 버스에 자리가 남으면
                    answerDate = curTime;
                    break;
                } else if (bus.size() == m) { // 버스가 만석이면
                    Date lastPerson = bus.get(bus.size() - 1); // 마지막에 탑승한 사람
                    Calendar answerCal = Calendar.getInstance();
                    answerCal.setTime(lastPerson);
                    answerCal.add(Calendar.MINUTE, -1);
                    answerDate = answerCal.getTime();
                }
            }
            // 시간 더하기(t분)
            cal.add(Calendar.MINUTE, t);
        }
        return df.format(answerDate);
    }
}

 

[참고]

1. 시간에 대한 오름차순으로 객체를 넣으려고 PriorityQueue를 사용했다. 

Comparator가 필요할까하여 구현했었는데, 그냥 PriorityQueue에 Date 객체를 바로 넣어도 오름차순으로 정렬이 되었다. 

 

∴ PriorityQueue는 Date 객체도 오름차순으로 정렬된다. 

// 1.Comparator 익명 클래스 구현
PriorityQueue<Date> pq = new PriorityQueue<>((o1, o2) -> o1.getTime() >= o2.getTime() ? 1 : -1);


// 2.Comparator 없이 default 
PriorityQueue<Date> pq = new PriorityQueue<>();

// 1,2 모두 Date객체 오름차순으로 정렬