악곱 == 악성곱슬

String, 투 포인터

---

이 문제는 주어진 문자열을 잘 파싱해서 푸는 구현 문제이다. 그리고 head, tail 을 통해 구간 내에 있는 원소 개수를 투 포인터를 이용해서 푸는 문제이다.

우선 시간이 H:M:S.f 꼴로 주어져서 datetime을 쓰고 싶은 충동이 생길 수 있으나, millisecond로 전환하여 푸는게 더 쉽다. 따라서 : 와 . 으로 파싱한 후 이를 끝나는 시간으로 저장한다.

그리고 소요된 시간을 빼서 시작 시간으로 구한다. 이 또한 float + s 로 이루어진 문자열인데 잘 파싱해서 계산한다. 여기서 2.0 2 0.251 등 여러 꼴이 second 형태로 주어지는데 이를 millisecond로 바꾸지 않아서 틀린점을 찾기 어려웠다.

이제 시작 시간과 끝나는 시간을 모두 역순으로 정렬하고, 시작 시간으로 head를 이동시키며 tail 은 head - 999를 해서 1초의 구간을 준다. 그리고 tail보다 작은 끝나는 시간이 있다면 모두 카운트에서 빼버리며 구현하면 간단하게 답을 구할 수 있다.

datetime의 사용에 익숙치 않다면 시간은 millisecond나 second등 작은 단위로 변환하여 풀면 간단하다는 것을 명심하자.

구현

---

def solution(lines):
    answer = 0

    start = []
    end = []
    # preprocessing
    for i in range(len(lines)):
        _, s, t = lines[i].split()
        hour, minute, tmp = s.split(":")
        sec, milli = tmp.split(".")
        end_time = int(hour)*60*60*1000 + int(minute)*60*1000 + int(sec)*1000 + int(milli)
        start_time = end_time - int(float(t[:-1])*1000) + 1
        end.append(end_time)
        start.append(start_time)

    start.sort(reverse=True)
    end.sort(reverse=True)
    # 투 포인터
    count = 0
    while start:
        head = start[-1]
        count += 1
        start.pop()
        tail = head - 999
        while end[-1] < tail:
            count -= 1
            end.pop()
        answer = max(answer, count)

    return answer

print(solution([
    "2016-09-15 20:59:57.421 0.351s",
    "2016-09-15 20:59:58.233 1.181s",
    "2016-09-15 20:59:58.299 0.8s",
    "2016-09-15 20:59:58.688 1.041s",
    "2016-09-15 20:59:59.591 1.412s",
    "2016-09-15 21:00:00.464 1.466s",
    "2016-09-15 21:00:00.741 1.581s",
    "2016-09-15 21:00:00.748 2.31s",
    "2016-09-15 21:00:00.966 0.381s",
    "2016-09-15 21:00:02.066 2.62s"]
))

print(solution([
    "2016-09-15 01:00:04.002 2.0s",
    "2016-09-15 01:00:07.000 2s"
]))