[프로그래머스_LV.3] 셔틀버스 (Java)
메서드를 3개나 만들다니..
요즘 알고리즘 풀 때 메모에 먼저 어떻게 풀지 작성하고 풀고있다.
항상 코딩테스트 볼 때, 시간이 얼마 없어! 생각하면서
무작정 푸는데, 곰곰이 생각하고 푸는 것이 더 도움이 되는 것 같다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/17678
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
알고리즘 설계 [접근 방법] : 구현
셔틀 버스의 개수 n이 최대 10이므로, 시간복잡도를 크게 신경쓰지 않고 구현으로 문제를 풀었다. 아무래도 시간이 문자열로 주어지다 보니, 문자열을 다루는 것이 익숙하지 않으면 어려울 것 같다.
풀이 과정
1.
가장 먼저, 크루가 도착하는 시간을 담은 배열 timetable을 정렬한다. 정렬이 되지 않은 상태에서 진행하다 보면 9:00에 탈 수 있는 사람도 10:00에 타야하고 이런 일이 발생하기 때문에 정렬을 해주었다.
2.
버스가 처음 출발하는 시간이 "09:00"이므로, 현재 버스가 도착하는 시간 변수인 cur을 "09:00"로 지정한다.
3.
셔틀 운행 간격이 t분이기 때문에, 다음 버스 도착시간을 계산해야 한다. 이것을 따로 메서드로 만들었다.
현재 시간을 분 단위로 변경한 뒤, t값을 더해준다.
그리고 그 값을 /60한 값을 시간으로, %60한 값을 분으로 계산한다.
4.
현재 버스 도착 시간을 안다면, 이 버스를 몇 명이 탈 수 있을지 계산해야한다.
따로 메서드를 만들었다.
현재 버스시간과 버스 타려고 기다리는 사람을 매개변수로 담아주고 서로의 시간을 비교한다.
만약 기다리고 있는 사람이 더 먼저 와있다면, queue에서 빼주고 max값을 -1해준다.
버스 하나 당 탈 수 있는 사람의 명수가 m(max)이므로, max가 0이 되거나 queue에 사람이 모두 없어진다면 반복문을 멈춘다.
5.
현재 버스가 막차이면서, 버스를 타야하는 크루들의 명수가 m보다 크다면 2가지가 발생한다.
크루들이 버스 도착시간 보다 일찍 도착할 경우, 아니라면 버스 도착 시간보다 늦게 도착하는 크루들이 많은 경우
전자라면, 콘은 다른 크루보다 일찍 도착해야하는 것이고 후자라면 버스 도착시간에 도착하면 되는 것이다.
stack을 생성하고, 버스 도착시간보다 일찍 도착한 크루들의 명수를 stack에 저장한다.
stack의 크기가 m보다 크다면, 콘은 마지막(stack.pop()) 사람보다 1분 일찍 도착해야 한다.
stack의 크기가 m보다 작다면, 콘은 버스 도착시간에 도착하면 된다.
6.
현재 버스가 막차이면서 버스를 타야하는 크루들의 명수가 m보다 작다면, 콘은 그냥 막차 버스시간에 도착하면 된다.
7.
막차가 아닐 경우에는 현재 버스에 탈 수 있는 인원이 몇명인지 센 후, 탈 수 있는 인원은 queue에서 제거한다.
코드
import java.util.*;
class Solution {
public String solution(int n, int t, int m, String[] timetable) {
String answer = "";
//1. 시간 정보 queue에 저장
PriorityQueue<String> queue = new PriorityQueue();
for(int i=0; i<timetable.length; i++){
queue.add(timetable[i]);
}
//2. 버스 출발 시간
String cur = "09:00";
for(int i=1; i<=n; i++){
//3. 현재 버스시간 계산
cur = timecheck(cur, i-1, t);
//5. 막차이면서, 콘이 다른 사람보다 더 빠르게 와야 하는 경우
if(i==n && m<=queue.size()) {
Stack<String> stack = new Stack();
int max = m;
String people = queue.peek();
//4. 버스가 도착하는 시간에 오는 사람이 몇명인지 세기
while(check(cur, people)) {
stack.add(queue.poll());
max--;
if(queue.isEmpty()) break;
else if(max<=0) break;
people = queue.peek();
}
//5. 버스가 도착하는 시간에 오는 사람이 m보다 적다면,
if(stack.size()<m) return cur;
//5. 버스가 도착하는 시간에 오는 사람이 m보다 많다면,
String last = stack.pop();
return bussafe(last);
}
//6. 막차이면서, 남아 있는 사람들이 적을 때
else if(i==n && queue.size()<m) {
return cur;
}
//7. 막차가 아니라면 그냥 보내기
else if(i!=n && m<=queue.size()) {
int max = m;
String people = queue.peek();
//4. 버스가 도착하는 시간에 오는 사람이 몇명인지 세기
while(check(cur, people)) {
queue.poll();
max--;
if(queue.isEmpty()) break;
else if(max<=0) break;
people = queue.peek();
}
}
//막차가 아니면서, 사람도 적을 때
else if(i!=n && queue.size()<m) {
continue;
}
}
return answer;
}
//4. 버스보다 먼저와있는지 확인
public static boolean check(String bus, String people){
String[] bustime = bus.split(":");
String[] peopletime = people.split(":");
if(Integer.parseInt(peopletime[0])==Integer.parseInt(bustime[0]))
return Integer.parseInt(peopletime[1])<=Integer.parseInt(bustime[1]);
else return Integer.parseInt(peopletime[0])<Integer.parseInt(bustime[0]);
}
//3. 버스 현재 시간 구하기
public static String timecheck(String time, int n, int t) {
String[] bustime = time.split(":");
int cur = (Integer.parseInt(bustime[0])*60)+Integer.parseInt(bustime[1]);
if(n==0) t=0;
int hour = (cur+t)/60;
int minute = (cur+t)%60;
return String.format("%02d:%02d", hour, minute);
}
//4. 마지막 사람보다 1분 빠르게 도착하기
public static String bussafe(String time) {
String[] last = time.split(":");
int corn = (Integer.parseInt(last[0])*60)+Integer.parseInt(last[1])-1;
int hour = (corn)/60;
int minute = (corn)%60;
return String.format("%02d:%02d", hour, minute);
}
}
(❁´◡`❁)
끝!