[Programmers] 1차 추석 트래픽

문제링크  👉  https://programmers.co.kr/learn/courses/30/lessons/17676

 

문제 이해 

응답 완료된 시간 정보와 처리 시간 정보가 (날짜 정보도 주어지지만 의미가 없음) 배열로 주어지고 초당 최대 처리량을 구하는 문제입니다. 문제의 맨 아래 부분의 그림을 보면, 초당 겹치는 처리부분이 최대 몇개냐를 구해야 합니다. 

문제 풀이

예제를 보고 처음엔 0.001초 소숫점 셋째 짜리까지 계산해야 하기 때문에 두가지 방법을 사용할 수 있다고 생각했습니다.

1. 1000을 곱해서 소수점을 지우고 계산한다.

2. swift의 DateFormatter 클래스와 Date 타입의 timeIntervalSince 메소드를 이용해서 시간 계산을 한다. 

저는 swift의 장점을 살릴 수 있는 문제겠구나 하며 2번 방법을 선택하였고 그 이후로 삽질을 정말 많이 했습니다.

 

날짜와 시간(시,분,초)이 주어지고 시작시간과 완료시간은 구했는데, 초당 최대 처리량을 구하다가 막혀버렸습니다. 

전혀 감이 오지 않더라구요.. 그래서 카카오 해설을 보고 풀이 방향을 잡을 수 있었습니다.

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

카카오 신입 공채 1차 코딩 테스트 문제 해설

 

0.001 단위로 모든 시간마다 처리량을 전부 계산을 해버리면,

1초를 계산하는데 1000번을 돌아 계산해야하고 이것을 n번 하루동안 계산을 해야합니다. (하루라는 것은 문제 조건에 나와있음)

하루 * N * 1000

= 24 * 60 * 60 * 1000 * N 

= 86400000 * N (1<=N<=2000)

보면 시간 초과가 나올 것이라고 예상할 수 있습니다.

 

그럼 다시 문제의 맨 아래 부분의 그림을 보면,

처리량이 변하는 부분은 응답을 시작하는 부분과 완료하는 부분 두 군데 뿐이라는 것을 알 수 있습니다. 

그 두 부분은 하나의 응답이므로 한 군데만 계산을 해도 되는데

완료 시간이 이미 오름차순으로 정렬되어 있는 것을 보아 완료 시간만 고려하면 된다를 알 수 있습니다.

각 응답 완료 시간마다 모든 응답 시간의 시작시간에서 1s만큼의 시간을 뺀 시각을 비교하여서 응답 완료 시간이 크다면 포함하면 됩니다.

 

응답들의 개수를 N이라 하면

각 응답마다 응답들을 한번씩 비교해가면 되니 

N * N , 시간 복잡도는 O(N^2)로 위의 경우보다 훨씬 줄게 됩니다.

 

But,,

위 2번 방법으로 처음에는 풀기 시작하였지만 테케 3번과 18번에서 계속 실패가 났습니다. 그래서 다른 언어로 푼 코드를 참고하였는데 1번방법을 선택했더라구요. 그래서 저도 1번 방법으로 바꿔보았고 통과했습니다.

2번 방법이 실패한 이유... 아직도 정확히는 모르겠지만 제가 내린 결론은 Date타입을 이용하여 계산하면 소숫점 셋째짜리뿐만 아니라 소숫점 넷째자리, 다섯째자리....  10번째 자리까지 더 정밀하게 계산이 되서 3번과 18번에서 오류 나는 것이라고 생각했습니다. 아닐 수도 있습니다.

 

코드 

문자 파싱해서 응답 시작 시간과 응답 완료 시간 구하기

시간 정보가 날짜 정보와 섞여 있으므로 적절한 정보를 얻기 위해 파싱해주어야 합니다. 

문자열 쪼개는 방법! 👉 2022.01.15 - [iOS] - [Swift] String Index 

파싱해주는 함수를 만들고 lines배열에서 원하는 위치의 정보를 빼내 응답 시작 시간 startIntTime과 응답 완료 시간 endIntTime을 구합니다. 밀리세컨드는 쉽게 계산해주기위해 시분초를 1000을 곱하고 밀리세컨드는 일의자리부터 백의자리로 계산합니다. 

 

처리시간은 시작시간과 끝시간을 포함하기 때문에 응답 시작 시간을 계산할 때 1을 더해주어야 합니다. (원래는 0.001을 더해야하는데 소숫점을 없애줬기 떄문에 1입니다.)

func getString(original: String, from: Int, to: Int) -> String {
    let startIndex = original.startIndex
    let start = original.index(startIndex, offsetBy: from)
    let end = original.index(startIndex, offsetBy: to)
    return String(original[start...end])
}

    var endIntTime = [Int]()
    var startIntTime = [Int]()

    lines.forEach {
        let strings = $0.split(separator: " ")
        let strings1 = String(strings[1])
        let hour = Int(getString(original: strings1, from: 0, to: 1))!
        let minute = Int(getString(original: strings1, from: 3, to: 4))!
        let second = Int(getString(original: strings1, from: 6, to: 7))!
        let millisecond =  Int(getString(original: strings1, from: 9, to: 11))!
        let timeInt: Int = (hour * 3600 + minute * 60 + second) * 1000 + millisecond
        endIntTime.append(timeInt)
        
        var strings2 = String(strings[2])
        strings2.removeLast()
        startIntTime.append(timeInt - Int(Double(strings2)! * 1000) + 1)
        
    }

 

응답 완료 시점마다 처리량 계산하기

완료 시점마다 모든 응답들의 시작 시간 - 1000(1초)를 비교하여 크다면 응답이 처리된다고 생각하고 더해주었습니다. 여기서 크거나 같다가 아니라 크다인 이유는 처리 시간에 시작 시간도 포함되기 떄문입니다. 같다면 시작 시간 + 1 부터 응답이 시작 되기 때문에 처리하면 안됩니다.

    var maxResult: Int = 0
    for i in 0...lines.count-1 {
        var count = 0
        let currentTime = endIntTime[i]
        for j in i...lines.count-1 {
            if currentTime > startIntTime[j] - 1000 {
                count += 1
            }
        }
        maxResult = max(maxResult, count)
    }

 

전체 코드 

 

import Foundation

func getString(original: String, from: Int, to: Int) -> String {
    let startIndex = original.startIndex
    let start = original.index(startIndex, offsetBy: from)
    let end = original.index(startIndex, offsetBy: to)
    return String(original[start...end])
}
func solution(_ lines:[String]) -> Int {
    var endIntTime = [Int]()
    var startIntTime = [Int]()

    lines.forEach {
        let strings = $0.split(separator: " ")
        let strings1 = String(strings[1])
        let hour = Int(getString(original: strings1, from: 0, to: 1))!
        let minute = Int(getString(original: strings1, from: 3, to: 4))!
        let second = Int(getString(original: strings1, from: 6, to: 7))!
        let millisecond =  Int(getString(original: strings1, from: 9, to: 11))!
        let timeInt: Int = (hour * 3600 + minute * 60 + second) * 1000 + millisecond
        endIntTime.append(timeInt)
        
        var strings2 = String(strings[2])
        strings2.removeLast()
        startIntTime.append(timeInt - Int(Double(strings2)! * 1000) + 1)
        
    }

    var maxResult: Int = 0
    for i in 0...lines.count-1 {
        var count = 0
        let currentTime = endIntTime[i]
        for j in i...lines.count-1 {
            if currentTime > startIntTime[j] - 1000 {
                count += 1
            }
        }
        maxResult = max(maxResult, count)
    }
    
    return maxResult
}