싸이버개강총회.swift(타임스탬프 형태의 문자열 비교)

소개

BOJ19583.swift

매번 보던 패턴과 풀이방법은 굳이 안올리는 편이라 알고리즘 풀이는 잘 올리진 않았습니다.

하지만 이번 문제는 되게 재밌게 풀었던 기억이 있어서 올렸습니다.

https://www.acmicpc.net/problem/19583

19583번: 싸이버개강총회

 

설명

문제를 다 읽고난 뒤에 생각해보면 특이한 점을 발견할 수 있습니다.

이 문제는 특이하게도 입력의 개수가 몇개인지 알 수 없고, 모든 입력이 종료가 되면 정답을 출력해야 합니다.

저는 개행문자를 마지막에 오는 것으로 가정하고 풀었는데 잘 풀렸습니다.

 

문제의 입력은 다음과 같이 입력됩니다.

22:00 23:00 23:30
21:30 malkoring
21:33 tolelom
21:34 minjae705
...

첫번째 줄은 개강총회 시작시간(S) / 개강총회 끝낸시간(E) / 스트리밍 종료시간(Q)으로 입력받습니다.

이 문제의 핵심은 개강총회 시작전에 댓글을 남기고 개강총회가 끝나고나서 댓글을 남긴 사람의 숫자를 구하는 것입니다.

따라서 시간 (00:00 ~ S) 와 (E ~ S) 구간 모두 댓글을 남긴 사람의 숫자를 구하면 됩니다.

 

풀이(1차 시도)

타임스탬프 문제에서 많이 헤멨던 경험이 많았는데 시간 비교를 위해 모든 시간을 분으로 변환해서 풀었습니다.

extension String {
    func convertTimeToMinute() -> Int {
        let t = self.split{ $0 == ":" }.map{ Int($0)! }
        return t[0] * 60 + t[1]
    }
}

let times = readLine()!.split{ $0 == " " }.map{ String($0).convertTimeToMinute() }
let (S,E,Q) = (times[0], times[1], times[2])

var enter = Set<String>()
var leave = Set<String>()

while let input = readLine()?.split(separator: " ").map({ String($0) }),
      !input.isEmpty {

    let timestamp = input[0].convertTimeToMinute()
    let userName = input[1]
    
    if (0...S).contains(timestamp) {
        enter.insert(userName)
    }
    
    if (E...Q).contains(timestamp) {
        leave.insert(userName)
    }
}

print(enter.intersection(leave).count)

String을 확장해서 "hh:mm"형태의 시간을 분 형태로 바꾸어주는 메소드를 추가해주었습니다.

 

반복문 탈출은 2가지 경우에 탈출하도록 하였습니다.

- while let을 사용해 입력이 없는 경우

- 개행문자가 입력으로 들어온 경우

 

입장시간내에 댓글을 작성한 사람들을 담을 enter 집합과 스트리밍 종료전까지 댓글을 작성한 사람을 담을 leave 집합을 만들어주었습니다. 각각의 집합에 해당하는 댓글을 해당 구간에 맞게 적절히 삽입해주었습니다.

마지막에 출력은 enter와 leave에 모두 이름이 존재하는 사람들의 숫자만큼을 출력해주었습니다.

그렇지만...

나름 깔끔하게 풀었다고 생각했던 문제였습니다.

시간을 처리해주는 메소드를 추가해주었고 가독성 좋게 코드를 작성했다고 생각합니다.

하지만 문제를 다 풀 고 난 뒤에 다른 사람(lyr8403)의 풀이를 보고 놀랐습니다...

 

이분께서 적용했던 기법을 활용한 풀이방법은 다음과 같습니다.

풀이(2차 시도)

let times = readLine()!.split{ $0 == " " }.map{ String($0) }
let (S,E,Q) = (times[0], times[1], times[2])

var enter = Set<String>()
var leave = Set<String>()

while let input = readLine()?.split(separator: " ").map({ String($0) }),
      !input.isEmpty {

    let timestamp = input[0]
    let userName = input[1]
    
    if timestamp <= S {
        enter.insert(userName)
    }
    
    if (E...Q).contains(timestamp) {
        leave.insert(userName)
    }
}

print(enter.intersection(leave).count)

 

위의 로직과 모두 똑같습니다.

달라진 점이라곤 시간을 직접 파싱해서 계산하지 않고 문자열을 직접 비교했단 점입니다.

사실 "24" > "123" 을 하게되면 true가 나온다는 사실을 알고있었지만 시간 비교에 써볼 생각은 못했던 것 같습니다.

알고리즘테스트에서 타임스탬프 문제가 나오면 시간을 많이 허비했었는데 이렇게 간단하게 해결할 수 있다는 점은 놀라운 것 같네요.

신기하게도 구간에 대해서도 비교가 가능 하단 점입니다. (E...Q).contains(timestamp)

생각보다 활용범위가 높은 기법인 것 같아 정리할겸 올리게되었습니다.

 

후기

틈틈히 알고리즘문제를 풀고있습니다.

일반적인 알고리즘 기법은 인터넷에 많이 올라오다보니 포스팅에 딱히 욕심히 나진 않았는데,

이번 문제같은 경우는 새로운 발견을 하게되어 올리게 되었습니다.

저처럼 타임스탬프나 시간비교에서 헤메셨던 분들께 도움이 되었으면 좋겠네요.

 

나아가 iOS 개발에서도 시간비교가 필요한 경우에 구체적인 시간(TimeInterval)이 필요한 것이 아니라 비교만 필요한 경우라면 파싱을 하지않고 간단하게 비교할 수 있을 것 같아 활용범위가 높을 것 같습니다.