[Week of Line Sweep] BOJ 2594

이전에 풀었던 BOJ 2190과 비슷한 문제였다.

fabichoi.tistory.com/52?category=899969

 

입력된 시간을 분 단위로 변경 및 시작시간 -10분, 종료 시간 +10분 처리.

중복되는 구간을 구한 다음에 처음부터 순회하면서 빈 시간을 구하면 끝.

 

여기서 중복되는 구간을 구할 때 삽질한 내용이 있다.

포함되는 경우를 꼬오오옥 고려해줘야 한다.

그렇지 않을 경우 중복 구간이 제대로 계산되지 않아서 WA(Wrong Answer)가 난다.

 

혹은 아예 중복구간을 따로 구하지 않고

쉬는 시간을 max로 구하는 로직으로 구현하면 된다.

 

작성된 코드는 아래와 같다.

if __name__ == "__main__":
    tt = []
    for _ in range(int(input())):
        a, b = input().split(' ')
        a = max(int(a[:2]) * 60 + int(a[2:4]) - 10, 600)
        b = min(int(b[:2]) * 60 + int(b[2:4]) + 10, 1320)
        tt.append([a,b])

    tt.sort()

    r = []
    r.append(tt.pop(0))
    index = 0

    while len(tt) > 0:
        t = tt.pop(0)
        if r[index][1] >= t[1] and r[index][0] <= t[0]:
            continue

        if r[index][1] >= t[0]:
            r[index][1] = t[1]
        else:
            index += 1
            r.append(t)

    r = [[600, 600]] + r + [[1320, 1320]]
    m = 0
    for i in range(1, len(r)):
        p = r[i][0] - r[i-1][1]
        m = max(m, p)

    print(m)

익숙한 유형이어서 금방 풀겠지 했는데

포함 구간의 함정으로(혹은 실수) 꽤 오래 걸렸던 문제였다..

 

다음에는 동일한 실수는 안 하길!