[92] 코딩테스트: [1차] 셔틀버스 자바 풀이 | 카카오 인턴십

코딩테스트 준비 92일차

 

오늘 풀 문제는 [1차]셔틀 버스이다.

 

해당 문제는 당연히 그리디지만 어려운 그리디..

 

 

[1차] 셔틀 버스

• Greedy
  • 셔틀에 타기 위해 도착해야 할 가장 늦은 시간
• 모든 도착 시간을 분 단위로 변환해 오름차순 정렬 => PriorityQueue
• 셔틀을 1대씩 시뮬레이션 -> 마지막 셔틀에 콘이 탈 수 있는지 판단
  • 만약 마지막 셔틀이 자리가 남았다면, 콘은 그 시간에 도착
  • 만약 자리가 없다면, 마지막으로 탄 사람보다 1분 일찍 도착

출처: 프로그래머스 셔틀버스 자바 풀이 카카오 인턴십

 

프로그래머스

 

 

if(i==n-1) {
        if(index == 0) {
            answer += "09:00";
        } else if(index < m) {
            answer += check2(list.get(index));
        }
    }
    for(int j=0; j<=index; j++) {
        list.remove(j);
    }
}

 

 

정답 코드

import java.util.*;

class Solution {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        
        for(int i=0; i<timetable.length; i++) {
            pq.add(check(timetable[i]));
        }
        
        int last = 0;
        int index = 0;
        for(int i=0; i<n; i++) {
            int curTime =540 + t*i;
            index = 0;
            
            while(!pq.isEmpty() && pq.peek()<=curTime && index<m) {
                last = pq.poll();
                index++;
            }
            
            if(i == n-1) {
                if(index < m) {
                    last = curTime;
                } else {
                    last -= 1;
                }
            }
        }

        return check2(last);
    }
    
    private int check(String t) {
        String[] time = t.split(":");
        return Integer.valueOf(time[0])*60+Integer.valueOf(time[1]);
    }
    
    private String check2(int t) {
        String a = String.valueOf(t/60);
        if(a.length() == 1) {
            a = "0"+a;
        }
        
        String b = String.valueOf(t%60);
        if(b.length() == 1) {
            b = "0"+b;
        }
        
        return a+":"+b;
    }
}