[프로그래머스] Swift - 카카오 [1차] 셔틀버스

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

프로그래머스

 

2023.07.28 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제가 길지만 핵심을 요약하면 다음과 같습니다.

1. 9시부터 t분 간격으로 n회 셔틀이 온다.
2. 콘이 매일 당일에 셔틀을 타야하는데 최대한 늦은 시간에 타야한다.

즉, 콘이 가장 늦게 셔틀을 타도록 하면 됩니다.

가장 늦게 타려면 당연히 마지막에 도착하는 셔틀버스의 마지막 자리에 타도록 콘의 도착시간을 설정하면 됩니다.

 

다른 크루들이 도착하는 시간들을 담은 배열이 주어지기 때문에 이것을 이용해 콘의 도착 시간을 구할 수 있습니다.

 

로직의 흐름

1. timetable을 분 단위로 바꾸어 Int로 저장
2. timetable을 오름차순으로 정렬 (먼저 도착하는 크루 순서대로 저장되도록)
3. 마지막 셔틀의 도착 시간 이후에 오는 크루들은 어차피 셔틀을 타지 못하기 때문에 tiemetable에서 제거 (문제 조건 중에 모든 크루는 23:59에 집에 들어간다는 조건이 있기 때문에 가능합니다.)
4. 마지막 셔틀 도착 이전 셔틀들을 반복문을 돌며 각각의 셔틀에서 데려갈 수 있는 크루들을 timetable에서 제거
5. 마지막 셔틀의 경우에는 콘이 m번째 자리로 셔틀을 탈 수 있도록 다른 크루들의 시간과 비교하여 결과값 구하기

6번 작업을 위해서 2가지를 고려하여 분기처리를 해야합니다.

1. 마지막 셔틀의 자리가 널널하다면 굳이 일찍 올 필요 없이 셔틀의 도착시간에 줄을 서도록 하면 됩니다. (예를 들어, 마지막 셔틀이 15시에 오고 5명이 정원인데 [14시, 14시10분]에 도착한 2명만 줄을 서고 있다면 15시에 줄 서도록 하면 됩니다!)
2. 마지막 셔틀의 자리가 부족하다면 m번째로 탑승할 사람보다 1분 더 일찍 오도록 하면 됩니다.

 

풀이

1. 시간을 Int와 String 형태로 변환하는 코드 구현

fileprivate extension String {
    var minutes: Int {
        let times = self.split(separator: ":")
        let hours = Int(times[0])! * 60
        let minutes = Int(times[1])!
        return hours + minutes
    }
}

fileprivate extension Int {
    var toTimeString: String {
        return String(format: "%02d:%02d", self/60, self%60)
    }
}

기초 자료형인 String과 Int에 extension을 통해 연산 속성을 추가하여 구현했습니다.

 

minutes는 "09:00"형태를 Int인 540(분)으로 바꿀 수 있도록 하는 속성입니다.

toTimeString은 반대로 Int형인 시간을 String으로 바꿉니다. 즉, 540을 "09:00" 형태로 바꾸는 코드입니다.

 

toTimeString과 같은 기능을 구현할 때는 직접 hour와 minutes를 나누어서 구하고 String으로 합치는 방법이 있지만 위처럼 String format을 이용하면 쉽게 구현이 가능합니다!

제가 사용한 "%02d"는 숫자를 0을 포함한 2자리 문자열로 바꾸는 format 형식입니다. (참고)

 

2. timetable 정렬 및 변수 선언

fileprivate func solution(_ n:Int, _ t:Int, _ m:Int, _ timetable:[String]) -> String {
    let startTime = "09:00".minutes
    let lastSuttleTime = startTime + (n-1)*t
    var timetable = timetable.map { $0.minutes }.sorted().filter { $0 <= lastSuttleTime }
    var result: Int = 0
    
    // 아래의 코드 구현 설명도 바로 이어집니다.
    // ...
}

• 우선 첫 셔틀의 도착 시간인 "09:00"을 Int형으로 변환하여 startTime에 담고 있습니다.
• lastShuttleTime은 마지막 셔틀의 도착 시간입니다. n에 1을 빼고 t를 곱하는 이유는 9시 정각에 오는 버스도 n회에 포함되기 때문입니다.
• timetable은 고차함수를 이용해 데이터를 가공했습니다.
  • map을 활용해 Int형의 시간으로 변환
  • sorted를 활용해 오름차순으로 정렬
  • filter를 활용해 마지막 셔틀 도착 시간보다 늦게 온 사람들의 정보는 제거

 

3. solution 함수 완성

fileprivate func solution(_ n:Int, _ t:Int, _ m:Int, _ timetable:[String]) -> String {
    let startTime = "09:00".minutes
    let lastSuttleTime = startTime + (n-1)*t
    var timetable = timetable.map { $0.minutes }.sorted().filter { $0 <= lastSuttleTime }
    var result: Int = 0
    
    for i in 0..<n {
        // 마지막 셔틀 전
        if i < n-1 {
            let shuttleTime = startTime + i*t
            var cnt = 0 // 탑승 인원 수
            while cnt < m && !timetable.isEmpty {
                let crewTime = timetable.first!
                if crewTime <= shuttleTime {
                    timetable.removeFirst()
                    cnt += 1
                } else {
                    break
                }
            }
        }
        
        // 마지막 셔틀
        if i == n-1 {
            // 셔틀의 마지막 자리에 타도록 하면 됨
            // 1. 자리가 널널하다면 셔틀의 도착시간에 줄 서도록
            // 2. 자리가 부족하다면 마지막 사람보다 1분 더 일찍 오도록
            if timetable.count < m || timetable[m-1] > lastSuttleTime {
                result = lastSuttleTime
            } else {
                result = timetable[m-1] - 1
            }
        }
    }
    
    return result.toTimeString
}

n회를 반복하며 셔틀이 사람들을 데러가는 로직을 구현했습니다.

 

i < n-1인 경우는 마지막 셔틀이 아닌 셔틀들입니다.

최대 m명 만큼 셔틀의 도착 시간 이전에 도착한 크루들을 데려가고 timetable에서 제거하도록 했습니다.

 

i == n-1인 경우는 마지막 셔틀인 경우고 이 셔틀에 콘이 탑승해야 합니다.

timetable.count < m || timetable[m-1] > lastSuttleTime의 의미는 마지막 셔틀의 자리가 남았기 때문에 콘이 이 셔틀이 도착하는 시간에 맞추어 줄을 서면 될 때를 의미합니다.

그렇지 않은 상황은 자리가 부족한 상황입니다. 따라서 콘은 m번째 탑승 예정객인 timetable[m-1] 시간보다 1분 더 일찍 줄을 서도록 하면됩니다.

 

마무리

구현 문제였습니다.

복잡한 알고리즘 테크닉은 필요하지 않았지만 요구 사항을 잘 분석하고 마지막 셔틀의 마지막 자리에 콘을 탑승시키도록 하는 아이디어를 떠올렸어야 합니다!

시간 데이터를 Int,String으로 변환하는 것이 구현 문제에서 자주 나오는 것 같습니다. 이 부분을 잘 기억해두면 좋을 것 같다는 생각이 들었습니다!