[프로그래머스] Swift - 추석 트래픽

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

프로그래머스

 

2023.09.29 기준 Level 3

 

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

 

아이디어

문제 조건

• lines 배열이 주어지며 각 요소는 2016-09-15 hh:mm:ss.sss의 형태인 S와 처리시간 T가 합쳐진 문자열 형태이다.
• 하나의 구간을 1초로 설정할 때 각 구간별로 처리하는 요청의 최대 개수를 리턴해야 한다.

위 그림과 같이 처리 기간들이 주어진다면 2번 구간(section)에 처리하는 요청이 7개로 최대이기 때문에 7을 리턴하면 된다.

(빨간색 구간들은 1초에 해당된다.)

 

 

우선 문제에서 시간 단위를 millisecond로 주었기 때문에 일반적인 문제에서 초 단위로 시간을 다루는 것과 다르게 별도의 처리를 해줘야 했다.

보통 이런 구간 문제는 슬라이딩 윈도우나 누적합으로 해결한 사례들이 있었는데 이 문제에서는 그렇게 하면 시간 초과가 발생한다.

날짜 자체는 2016-09-15인 하루로 고정되지만 ms 단위이기 때문에 24*60*60*1000 = 86,400,000 번의 연산이 발생할 수 있기 때문이다.

 

대신, lines 배열의 크기가 최대 2000개로 작은 값으로 주어졌다.

 

여기서 힌트를 얻었는데 1ms 단위로 구간을 움직이며 요청 개수를 구하는 것이 아니라 lines를 탐색하며 특정 구간에서 동시에 처리한 line들의 개수를 구하면 좋겠다는 아이디어였다.

 

먼저 문제에서 주어진 시간 포맷을 ms단위로 바꿨다.

2016-09-15는 필요 없는 데이터이기 때문에 삭제했고 hh:mm:ss.sss 에서 1000을 곱하고 시각에 60*60, 분에 60을 곱한다음 전부 더하여 ms 단위로 변환하였다. (결과적으로 Int 타입으로 변환 한 것)

 

Int로 변환한 line들을 요청 시작 시간과 끝 시간을 구하여 Tuple로 변환하였다.

typealias Line = (start: Int, end: Int) 형태이다.

Line.start는 요청 처리 시작 시간 (ms 단위)

Line.end는 요청 처리 끝 시간 (ms 단위)

로 나타낸 것이다.

 

이제 변환된 값들을 바탕으로 특정 구간안에서 몇개의 요청이 처리되었는지를 구해야 했다.

여기서 이 문제의 핵심을 파악해야 했다.

중요한건 요청이 시작된 시각과 끝난 시각이다.

즉, 요청량이 변하는 순간은 각 요청의 시작과 끝 부분 뿐이다.

만약 시작 시간이 3602003이고 끝 시간이 3604002라면

3602003에 요청량이 1 증가하고 3604003에 1 감소한다.

 

우리는 시간 초과를 방지하기 위해 변화가 발생하는 구간에 집중해야 한다. ➡️ 요청 시작 시각부터 1초 구간과 요청 끝 시각부터 1초 구간만 비교하면 된다.

 

lines 배열을 순회하며 각 line의 시작 시간으로부터 1초인 구간에 처리한 요청의 개수를 구하고 마찬가지로 line의 끝 시간으로부터 1초인 구간에 처리한 요청의 개수를 각각 구한다. 이렇게 구한 2가지 count 값이 해당 line으로 인해 요청량이 변동했을 때의 경우의 수를 모두 구한 것이다.

지금까지의 max 값과 이 값들 중에서 더 큰 값을 max로 저장하면 된다.

 

여기서 한가지 의문이 생길 수 있다.

만약 이 그림과 같은 상황이고 lines를 순회하며 요청1인 line을 기준으로 비교하는 상황이 왔다고 가정하자

앞서 설명한 방식대로 요청 시작으로부터 1초와 끝 시각으로부터 1초의 구간만 비교하게 되면 첫번째와 마지막 초록색 구간만 비교하게 된다.

따라서 해당 구간에서 처리한 요청 개수는 둘 다 2이고 max도 2로 갱신된다.

하지만 실제로는 우리가 계산하지 않은 구간인 두 번째 초록색 구간에서 4개의 요청을 처리했기 때문에 이것이 max가 되어야 한다.

이 영억을 빼고 계산했기 때문에 이 로직이 틀리다고 생각할 수 있다.

 

하지만 이 로직은 틀리지 않았다.

왜냐하면 저 두 번째 초록색 영역에서 계산된 4는 결국 요청 3을 기준으로 계산할 때 계산되는 영역이기 때문이다.

즉, 요청 1을 기준으로 시작과 끝을 비교할 때는 누락된 영역이지만 요청 3을 기준으로 시작과 끝의 1초의 영역을 기준으로 계산할 때는 저 구간이 포함되어 결국 언젠가 max가 제대로 갱신된다.

이는 요청량의 변화가 각 요청의 시작 부붙과 끝 부분에서만 발생하기 때문이다.

 

 

 

풀이

1. typealias 선언 (시간과 구간)

fileprivate typealias Line = (start: Int, end: Int)
fileprivate typealias Section = (start: Int, end: Int)

이 문제처럼 시작 시간과 끝 시간을 다루는 문제에서는 투플 형태로 관리하면 편한 것 같다.

따라서 typealias로 투플을 정의했다.

Line은 각 요청을 의미하고 Section은 1초의 구간을 의미한다.

 

2. 시간 변환 함수 구현

fileprivate func convertToMilliseconds(timeStr: String) -> Line {
    var timeStr = timeStr
    timeStr.removeLast()
    let components = timeStr.components(separatedBy: " ")
    let s = components[1]
    let t = Double(components[2])!
    
    let endTime = s.toMilliseconds
    let startTime = endTime - Int(t*1000) + 1
    
    return (startTime, endTime)
}

fileprivate extension String {
    var toMilliseconds: Int {
        let hourMinuteSecond = self.components(separatedBy: ":").map { Double($0)! * 1000 }.map { Int($0) }
        let hour = hourMinuteSecond[0]
        let minute = hourMinuteSecond[1]
        let seconds = hourMinuteSecond[2]
                
        return hour*60*60 + minute*60 + seconds
    }
}

문제에서는 문자열 형태로 line을 제공하기 때문에 이것을 ms단위로 변환하는 함수를 구현했다.

 

3. numOfTaskInSection 함수 구현

fileprivate func numOfTaskInSection(section: Section, lines: [Line]) -> Int {
    var cnt = 0
    
    for line in lines {
        if line.start > section.end || line.end < section.start {
            continue
        }
        cnt += 1
    }
    
    return cnt
}

특정 Section(1초 구간)에서 처리한 요청의 개수를 구하는 함수이다.

lines를 순회하며 section에 포함된 line을 찾으면 cnt를 1씩 증가시킨다.

 

4. solution 함수 구현

fileprivate func solution(_ lines:[String]) -> Int {
    let lines = lines.map { convertToMilliseconds(timeStr: $0) }
    var result = 0
    
    for line in lines {
        let start = line.start
        let end = line.end
        
        let sections: [Section] = [(start, start + 999), (end, end + 999)]
        
        for section in sections {
            let cnt = numOfTaskInSection(section: section, lines: lines)
            result = max(result, cnt)
        }
    }
    
    return result
}

1. 문자열 배열인 lines를 Line 타입의 배열로 매핑한다.
2. lines를 순회하며 해당 line의 시작 1초 구간과 끝 1초 구간에서 처리한 요청(task)개수를 구한다.
3. 2에서 구한 값과 기존에 저장하고 있던 result를 비교하여 더 큰 값을 result로 갱신한다.
4. result를 리턴한다.

 

 

 

마무리

아이디어를 떠올리는 것이 쉽지 않았다.

막상 풀고 나니 코드 자체는 특별한 알고리즘 기법이 필요하지 않았고 기본적인 문법만 알고 있어도 풀 수 있었다.

 

하지만 각 요청의 시작과 끝을 각 구간의 시작 시간으로 하여 요청 별로 2번의 비교만 하면 된다는 아이디어가 필요했다.

이렇게 하면 2*(N^2)의 연산으로 해결이 되고 이 문제에서 N은 최대 2000이기 때문에 시간 초과가 절대 발생하지 않는다.

빅오로 표현하면 O(N^2)이다.