프로그래머스 Lv.3) [1차] 셔틀버스

2018 KAKAO BLIND RECRUITMENT

셔틀버스

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

풀이

카카오 문제 중, 추석 트래픽을 풀 때 시간 문자열을 int형으로 변환하여 푼 경험 덕분인지 쉽게 풀었다.

우선, timetable에 저장된 시간 문자열을 시간과 분에 따라 int형으로 값을 저장해주었다. (시간 * 60 + 분)

이후, 문제 예제를 보면 앞서 줄 서있는 사람이 있더라도 시간이 버스 출발 시간마다 꽉 채워 타는 것이 아닌 경우가 있어서, 직접 확인을 하면서 마지막 버스를 타기 전 대기열들을 다 빼주었다. (답은 최대한 늦게 출근하는 것이기 때문에)

 

위의 과정을 거쳐 마지막 버스를 기다리는 대기열만 남겼다.

만약 남은 대기열이, 한번에 탈 수 있는 m명 미만으로 남았다면, 마지막 버스 시간을 저장해주었다.

같거나 많은 경우에는 앞에서 부터 m명 중에, 가장 마지막으로 타는 사람의 시간을 저장해주었다.

이 때, 유의해야하는 점은 막차 이후에 줄 선 사람들이 입력으로 주어지는 경우가 있다는 것이었다.

 

그래서 m만큼 반복문을 돌면서, 시간의 최대 값을 찾아주었고, 이 시간이 막차 시간 이후라면 막차시간을 저장해주었다.

(앞에 대기열이 있어도, m번 째 사람은 어차피 못탈 것이기 때문)

위의 경우가 아니라면, 마지막으로 타는 사람보다 1분 빠른 시간을 저장해주었다.

이후, 시간을 문자열로 변환해 답을 저장했다.

 

추가적으로 설명할 부분이, 중간에 int형 변수 bus를 540으로 초기화한 부분일 것 같다.

처음 시간 문자열을 변환할 때, 시간*60 + 분으로 저장해줬다. 이에 따라, 첫 차의 시간 09:00를 변환하면 540이 된다.(9*60)

 

로직

1. 입력 받은 시간 문자열을 정수형 변수로 변환하여 우선순위 큐에 저장한다.

2. 최대한 늦게 출근하는 것이 목표기 때문에, 막차 이전에 탈 수 있는 사람들은 대기열에서 제거해준다.

3. 막차의 대기열을 확인하고, 줄이 입력받은 m명보다 작다면 막차시간에 맞추어 답을 저장해준다.

4. m명 이상이라면, 마지막으로 탈 수 있는 사람보다 1분 빨리 도착하게 설정한다.

 4-1. 단, 마지막으로 탈 수 있는 대기열에 막차시간 이후에 도착해있는 사람이 저장되어있다면, 막차시간을 저장한다.

 

코드

import java.util.PriorityQueue;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        PriorityQueue<MyTime> crewQ = new PriorityQueue<>();
        for(String timeStr : timetable) {
            crewQ.offer(new MyTime(timeStr));
        }
        
        int bus = 540;
        // 앞에 대기열 다 빼내기
        for(int turn =0; turn<n-1; turn++) {
            for(int i=0; i<m; i++) {
                if(crewQ.peek().time <= bus+turn*t) {
                    crewQ.poll();
                }
            }
        }
        
        int lastTime = bus+(n-1)*t;
        if(crewQ.size() < m) {  // 남은 대기열이 제일 늦게가도 탈 수 있으면
            answer = getStrTime(lastTime);
        } else {    // 여기서 탐색해야함
            int max =0;
            for(int i=0; i<m; i++) {
                max = Math.max(max, crewQ.poll().time);
            }
            if(max > lastTime) {
                max = lastTime;
            } else {
                max--;
            }
            answer = getStrTime(max);
        }
        
        return answer;
    }
    
    private String getStrTime(int time) {
        StringBuffer sb =  new StringBuffer();
        // time / 60  ~> 시간
        int hour = time/60;
        int min = time%60;
        if(hour <10) {
            sb.append("0");
        }
        sb.append(String.valueOf(hour));
        sb.append(":");
        if(min < 10) {
            sb.append("0");
        }
        sb.append(String.valueOf(min));
        return sb.toString();
    }
}

class MyTime implements Comparable<MyTime> {
    int time;
    
    public MyTime(String timeStr) {
        this.time = Integer.parseInt(timeStr.split(":")[0])*60 + Integer.parseInt(timeStr.split(":")[1]);
    }
    
    @Override
    public int compareTo(MyTime t) {
        return this.time > t.time ? 1 : -1;
    }
}