[프로그래머스/Swift] 155651번 - 호텔 대실

🔗 문제 링크

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

💡 구현 아이디어

1. 대실 시작시간과 종료시간을 각 (시, 분)으로 분리
2. 현재 시간 = 시작시간과 종료시간 중 작은 값으로 지정
3. 현재 시간과 가장 빠른 시간과 같을때 시작시간이면 객실 수 +1, 종료시간이면 객실 수 -1
4. 객실 수 +- 해주고 최대 객실 수 와 비교 해서 더 큰 값 저장
5. 시작시간 배열을 전부 확인하면 종료 → 종료시간 확인을 더 해도 최대값에는 영향이 없기 때문
6. 결과값 반환

💻 코드

import Foundation

func solution(_ book_time:[[String]]) -> Int {
    
    var result: Int = 0 // 가장 방을 많이 쓸때의 방개수
    var room: Int = 0 // 사용 중인 방 개수
    
    var startTime: [(Int, Int)] = [] // 대실 시작시간 (시, 분)
    var endTime: [(Int, Int)] = [] // 대실 종료시간 (시, 분) - 청소시간 포함 
    
    // 대실 시작시간과 종료시간(+청소시간)으로 분리
    for time in book_time {
        let start = time[0].split(separator: ":").map{ String($0) }
        let startH: Int = Int(start[0])!
        let startM: Int = Int(start[1])!
        startTime.append((startH, startM)) // 시작시간 추가
        
        let end = time[1].split(separator: ":").map{ String($0) }
        let endH: Int = Int(end[0])! + (Int(end[1])! + 10) / 60
        let endM: Int = (Int(end[1])! + 10) % 60
        endTime.append((endH, endM))
    }
    
    // startTime과 endTime은 정렬 필요
    startTime = startTime.sorted(by: {
        if $0.0 == $1.0 {
            return $0.1 < $1.1
        }
        return $0.0 < $1.0
    })
    
    endTime = endTime.sorted(by: {
        if $0.0 == $1.0 {
            return $0.1 < $1.1
        }
        return $0.0 < $1.0
    })
    
    // 시작시간이 비어있지 않으면 종료시간도 비어있지 않음 -> 시작 시간만 확인
    while !startTime.isEmpty {
        if let start = startTime.first, let end = endTime.first {
            let time: (Int, Int) = nowTimeCheck(start, end)
            
            if time == start {
                room += 1
                startTime.removeFirst()
            }
            
            if time == end {
                room -= 1
                endTime.removeFirst()
            }
    
            result = max(result, room)
        }
    }
    // 종료시간을 확인해도 최대 방개수는 줄어들기만 하니 따로 확인필요X
    
    return result
}

// 대실 시작시간과 종료시간중에 더 작은 시간을 반환
func nowTimeCheck(_ start: (Int, Int), _ end: (Int, Int)) -> (Int, Int) {
    
    // H로 비교
    if start.0 < end.0 { return start }
    if start.0 > end.0 { return end }
    
    // M으로 비교
    if start.1 < end.1 { return start }
    if start.1 > end.1 { return end }
    
    return start
}

❌ 틀린 이유 및 틀린 부분

⏳ 시간 복잡도

• 자체 알고리즘의 시간은 O(N)이지만 내부적으로 removeFirst가 들어가므로 O(N^2)으로 생각
• 이부분은 removeFirst를 쓰지 않는 코드를 생각해 둘 필요가 있다

📌 풀이 또는 기억할 정보

• 추가적인 생각으로 시간을 초로 전부 바꾸고 배열에 저장할때 (바꾼 초, 시작or종료)의 튜플 배열로 생성하고 O(N)의 형식으로 반복을 한번만 하면서 개수를 확인하면 될듯 하다
• 다른사람의 경우 배열을 24(시) * 60(분) = 1440 개로 만들어서 시작 시간에 요소+1, 종료 시간에 요소-1로 해주고 앞에서 부터 확인하면서 최대 개수를 찾는 경우도 있었다.