[프로그래머스] [1차] 셔틀버스 (자바)

 

셔틀버스

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

ntmtimetableanswer

1	1	5	[08:00, 08:01, 08:02, 08:03]	09:00
2	10	2	[09:10, 09:09, 08:00]	09:09
2	1	2	[09:00, 09:00, 09:00, 09:00]	08:59
1	1	5	[00:01, 00:01, 00:01, 00:01, 00:01]	00:00
1	1	1	[23:59]	09:00
10	60	45	[23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59]	18:00

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

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

 

프로그래머스는 문제 캡처가 불편하네요.

 

이 문제의 정답률은 약 27%입니다. 2번째로 낮다고 합니다.

 

이 문제는 버스가 n대 있고, 배차 간격이 t, 버스 1대에 탑승 가능한 인원이 m입니다.

주인공인 콘이 버스를 탈 수 있는 가장 늦은 시간을 구하는 문제입니다.

 

이 문제의 포인트는 마지막 버스에 있습니다.

마지막 버스에 자리가 남는가?

마지막 버스에 자리가 꽉 차는가?

이 두가지 경우만 보면 됩니다.

 

우선 timetable은 Time이라는 클래스를 만들어서 PriorityQueue(pq)에 넣었습니다.

Time을 Comparable하게 생성하여 오름차순으로 정렬되게 해 줬습니다.

버스가 올 때마다 탑승 가능한(도착해 있고 자리가 있음) 인원을 넣어줍니다(pq에서 제거).

콘의 시간을 항상 마지막으로 탑승한 인원의 시간으로 갱신해줍니다.(밑에서 설명)

 

마지막 버스가 왔을 때 버스에 자리가 남는다면 콘의 시간은 마지막 버스가 도착한 시간이 될 것이고,

사람이 가득 찼다면 마지막으로 탑승한 사람보다 1분 일찍 오면 됩니다.

 

마지막 버스에 3명이 탑승 가능하고 08:00, 08:01, 08:03 이라면 08:02에 콘이 오면 되겠죠.

3명 탑승 가능하지만 2명만 와있다면 버스 도착 시간인 09:00에 콘이 오면 됩니다.

---

전역 변수 

pq = 대기 중인 사람들의 도착 시간

answer = 콘의 도착 시간

메소드

void main 

solution 시작 (solution 호출)

String solution

사람들의 도착시간을 정제해서 pq에 넣어줍니다. 넣는 과정에서 오름차순 정렬이 됩니다.

answer 반환.(bus 호출)

void bus

각 버스마다 사람을 태웁니다. 총 n대의 버스로 t의 배차 간격을 두고 각 버스는 m명까지 탑승 가능합니다.

버스에 승차가 가능하면(pq.peek과 bus를 비교) pq.poll을 통해 1명을 pq에서 제거합니다.

승차와 동시에 버스에 탑승한 인원인 people을 1 증가시켜줍니다.

버스가 출발했다면 다음 버스 시간으로 갱신해줍니다.

마지막 버스일 때,

1. 사람이 가득 차있다. => 콘의 시간은 마지막 탑승 인원의 도착시간 -1분

2. 자리가 남는다. => 콘의 시간은 마지막 버스 도착 시간

class Time

h, m을 가집니다. 각 시간과 분입니다.

생성자에서 분이 정상 값이 아니라면 적절히 처리해서 생성해줍니다.

pq에서 정렬을 해야 하므로 Comparable 인터페이스를 구현합니다.

 

import java.util.PriorityQueue;

public class pm3_2 {

	public static void main(String[] args) {
		String s[] = {"23:59"};

		System.out.println(solution(1,1, 1, s));
	}

	static PriorityQueue<Time> pq = new PriorityQueue<Time>();
	static String answer = "";
	public static String solution(int n, int t, int m, String[] Timetable) {
		for(int i = 0; i < Timetable.length; i++) {
			String s[] = Timetable[i].split(":");
			pq.add(new Time(Integer.parseInt(s[0]), Integer.parseInt(s[1])));
		}

		bus(n, t, m);
		return answer;
	}

	public static void bus(int n, int t, int m) {
		Time bus = new Time(9, 0);
		Time corn = new Time(9, 0);

		//버스의 개수
		for(int i = 0; i < n; i++) {
			int people = 0;
			
			//각 버스마다 탑승하는 인원(0~m)
			for(int j = 0; j < m; j++) {
				if(!pq.isEmpty()) {
					Time temp = pq.peek();

					//버스에 탑승 가능한 인원
					if(bus.compareTo(temp) >= 0) {
						corn = pq.poll();
						people++;
					}
				}
				//마지막 버스에 사람이 가득 찬 경우
				if(i == n-1 && people == m) {
					corn = new Time(corn.h, corn.m-1);
				}
				//마지막 버스에 자리가 남는 경우
				else if(i == n-1 && people < m) {
					corn = new Time(bus.h, bus.m);
				}
			}
			//다음 버스 도착 시간
			bus = new Time(bus.h, bus.m+t);
		}
		//콘의 시간을 String으로 정제
		answer += (corn.h < 10 ? "0"+corn.h : corn.h)+":"+ (corn.m<10?"0"+corn.m : corn.m);
	}

	static class Time implements Comparable<Time>{
		int h, m;

		Time(int h, int m) {
			if(m < 0) {
				m += 60;
				h--;
			}

			if(m >= 60) {
				m -= 60;
				h++;
			}
			this.h = h;
			this.m = m;
		}

		public int compareTo(Time o) {
			if(h == o.h)
				return m - o.m;
			return h-o.h;
		}
	}
}