문제 풀이 아이디어

콘의 목표

콘의 목표는 가장 늦게 버스를 타는 것입니다. 즉 콘의 목표를 만족하기 위해서는 아래의 조건이 만족 되어야 합니다.

1. 무조건 막차를 타야한다. (가장 늦게 오는 버스이므로)
2. 여러 명이 막차를 탄다만 가장 늦게 타야한다. (최대한 늦게 타야하므로)

막차에 타는 사람 구하기

1번, 2번 조건을 감안했을 때 우리가 필요한 것은 막차에 타는 사람들이 줄을 서는 시간입니다. 하지만 막차 시간만 가지고 계산해서는 막차에 타는 사람들을 구할 수는 없습니다. 막차의 앞차가 가득차서 일찍 도착했음에도 막차에 타야하는 사람이 있을 수 있기 때문입니다. 막차의 앞차도 막차의 앞앞차보다 먼저 도착했음에도 못 타는 사람이 있을 수 있습니다.

결국 첫 차부터 각각의 차에 어떤 사람이 타는지 모두 구해야 막차에 타는 사람을 구할 수 있습니다.

막차를 타는 경우 2가지

자 막차에 타는 사람을 구했습니다. 이 때 두 가지 경우의 수가 발생합니다.

1. 막차에 자리가 남는 경우
2. 막차가 가득찬 경우

1번의 경우는 콘은 느긋하게 막차의 시간에 맞추어 오면 됩니다. 문제는 2번의 경우입니다. 이 경우는 콘이 막차 시간에 도착하면 막차를 탈 수 없습니다. 콘이 막차에 타기 위해서는 마지막 사람을 끌어내고(?) 타야합니다. 즉 마지막 사람보다 1분 일찍 와야 막차를 탈 수 있습니다.

코드

위 문제 풀이 아이디어를 코드로 구현했습니다. 각각의 버스에 타는 사람들의 도착시간을 나타내기 위해 이중 배열을 사용했습니다.

import Foundation

// 시간: String을 Int로
func parseTime(_ s: String) -> Int {
    let hm = s.split(separator: ":").map { Int($0)! }
    return hm[0] * 60 + hm[1]
}

// 시간: Int를 String으로
func parseInt(_ time: Int) -> String {
    String(format: "%02d:%02d", time / 60, time % 60) //👉 import Foundation 해야 함!
}

// 버스 시간표 만들어주는 함수 (각각 몇시에 출발하는지)
func busTimes(_ n: Int, _ t: Int) -> [Int] {
    let start = 540
    var result = [Int]()

    for i in 0..<n {
        result.append(start + t * i)
    }

    return result
}

func solution(_ n:Int, _ t:Int, _ m:Int, _ timetable:[String]) -> String {

    // 사람들이 줄 서는 시간을 파싱 & 정렬
    let people = timetable.map { parseTime($0) }.sorted()
    // 버스 시간표
    let buses = busTimes(n, t)

    // i번째 버스에 누가 타는지 나타내는 배열
        // rideTable[0] = 첫 차에 타는 사람들의 도착 시간
				// rideTable[n - 1] = 막차에 타는 사람들의 도착 시간
    var rideTable = [[Int]]()
    
    // 지금 버스를 탈 사람의 index
    var p = 0

    // 모든 버스를 순환
    for bus in buses {
        // 이번 버스를 탈 사람들의 Array
        var nowRide = [Int]()
        // stop할 때까지 버스를 한 명씩 태운다
        while p < people.count // 사람이 모두 타면 stop
                && nowRide.count < m // 지금 탈 버스가 꽉 차면 stop
                && people[p] <= bus { // 다음 사람이 버스 시간 보다 늦게 오면 stop
            nowRide.append(people[p])
            p += 1
        }
        // 이번 버스에 탄 사람을 rideTable에 저장
        rideTable.append(nowRide)
    }

    // 셔틀에 자리가 있을 때 -> 마지막 버스 시간에 딱 맞춰 간다
    if rideTable[n - 1].count < m {
        return parseInt(buses[n - 1])
    // 마지막 셔틀에 자리가 없을 때 -> 마지막 버스의 마지막 자리에 탄 사람보다 1분 일찍 간다
    } else {
        return parseInt(rideTable[n - 1][m - 1] - 1)
    }
}

Tips) 문자 → 정수 → 문자

위의 문제에서 중요한 부분 중에 하나는 시간을 나타내는 문자열을 정수로 그리고 다시 문자열로 파싱하는 과정입니다. 그 과정에서 사용한 메소드들을 복습해보도록 하겠습니다.

문자 → 정수

split(separator: " ")

문자열을 원하는 문자열을 기준으로 나누는 메소드입니다. components(separatedBy: " ") 같은 메소드도 있습니다만 해당 메소드는 import Foundation이 필수이고 실행 시간도 더 깁니다.

func parseTime(_ s: String) -> Int {
    let hm = s.split(separator: ":").map { Int($0)! }
    return hm[0] * 60 + hm[1]
}

prefix(), suffix()

위 함수를 아래와 같이 바꿀 수도 있습니다. 처음 n개의 문자열을 반환하는 prefix, 마지막 n개의 문자열을 반환하는 suffix를 활용한 방법입니다.

func parseTime(_ s: String) -> Int {
    let h = Int(s.prefix(2))!
    let m = Int(s.suffix(2))!
    return h * 60 + m
}

정수 → 문자

String(format: )

String 타입의 initializer의 하나로 원하는 포맷과 변수를 이용해서 String을 만드는 방법입니다.

func parseInt(_ time: Int) -> String {
    String(format: "%02d:%02d", time / 60, time % 60) //👉 import Foundation 해야 함!
}