[프로그래머스] 셔틀버스 (Swift)

[프로그래머스] 셔틀버스 (Swift)

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

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

풀이

문제 풀이를 위해 고려해야할 점을 정리해보겠습니다.

1. 모든 셔틀버스가 꽉 찼을때

이 경우에는 탈 자리가 없기 때문에 마지막 버스에 마지막으로 탑승한 사람보다 빨리 도착해야 합니다.

 

1분만 빨리 도착해도 되기 때문에 마지막 탑승자보다 1분 빠른 시간이 도착 시간이 됩니다.

2. 셔틀버스가 꽉 차지 않았을때

정원이 3명인 버스가 3번 도착한다고 가정하고, 대기 승객이 5명이라고 가정하겠습니다.

 

이 때 1번 버스에는 3명이 모두 탑승할 것이고, 2번 버스에는 2명이 탑승하여 한 자리가 남아 2번 버스의 도착 시간이 정답이 될 수 있다고 착각할 수 있습니다.

 

하지만 저희는 무조건 가장 마지막 탑승 시간을 구해야하기 때문에 3번 버스의 도착 시간을 구해야 합니다.

 

그렇기 때문에 이 경우에는 가장 마지막 버스가 도착하는 시간이 정답이 됩니다.

 

---

이 2가지를 고려하면 문제를 해결할 수 있습니다.

 

일단 도착시간이 정렬되어있지 않기 때문에 저는 도착시간을 모두 정렬해준 후, 분 단위로 환산하여 Queue 에 삽입해주었습니다.

 

그 다음 버스가 도착할 때마다 탑승이 가능한 승객들을 Queue 에서 꺼냈습니다. 해당 작업을 반복하면 결국 위의 2번 조건을 만족하는지, 만족하지 않는지 확인할 수 있습니다.

 

위에서 설명한 2번 조건을 그대로 구현한다면 문제를 해결할 수 있습니다.

코드

	import Foundation
	func solution(_ n: Int, _ interval: Int, _ passengers: Int, _ timetable: [String]) -> String {
	var queue = DoubleStackQueue<Int>() // 기다리는 승객들
	var time = 540 // 시간
	var last = -1 // 가장 마지막 승객이 탄 시간
	var board = 0 // 한 버스에 승객이 몇명 탔는지
	// 정렬 후 큐에 삽입
	timetable.sorted().forEach { time in
	let split = time.split(separator: ":").map { Int($0)! }
	queue.enqueue(split[0] * 60 + split[1])
	}
	for _ in 0 ..< n {
	board = 0
	// 탑승할 수 있는 승객들은 큐에서 삭제
	for _ in 0 ..< passengers {
	if !queue.isEmpty {
	if queue.front! <= time {
	last = queue.dequeue()!
	board += 1
	}
	}
	}
	time += interval
	}
	// 만약 버스가 꽉찼다면 마지막 승객보다 1분 빠른 시간
	if board == passengers {
	return generateTime(last - 1)
	}
	// 아니라면 마지막 버스가 도착하는 시간
	else {
	return generateTime(time - interval)
	}
	}
	// 시간 형식
	func generateTime(_ time: Int) -> String {
	var result = ""
	let hour = time / 60
	let min = time % 60
	result += hour < 10 ? "0\(hour):" : "\(hour):"
	result += min < 10 ? "0\(min)" : "\(min)"
	return result
	}
	// 큐
	struct DoubleStackQueue<T> {
	var inbox: [T] = []
	var outbox: [T] = []
	var isEmpty: Bool {
	return inbox.isEmpty && outbox.isEmpty
	}
	var count: Int {
	return inbox.count + outbox.count
	}
	var front: T? {
	return outbox.last ?? inbox.first
	}
	mutating func enqueue(_ input: T) {
	inbox.append(input)
	}
	@discardableResult
	mutating func dequeue() -> T? {
	if outbox.isEmpty {
	outbox = inbox.reversed()
	inbox.removeAll()
	}
	return outbox.popLast()
	}
	}

view raw programmers_셔틀버스.swift hosted with ❤ by GitHub