[Week of Line Sweep] BOJ 2170

당분간은 Line Sweep이라고 하는 알고리즘 문제를 풀어볼 예정이다.

일반적으로 가장 가까운 두 점을 찾거나, 중복되는 선분을 정리해서 전체 길이를 구하는 등의 문제 등이 있다.

 

최근에 풀기를 시도한 문제 유형이 바로 이거였는데 어찌 풀까 고민만 하다가 결국 못 풀었다.

답답해서 어떤 유형인지 찾아보니 개념도 그다지 어렵지 않고 내가 가끔씩 못 풀고 넘어가는 유형 중에 하나기도 해서 이 유형을 먼저 정복해보려고 한다.

 

어떤 학습이든 익숙해지면 되는 거니까 감이 안 오면 바로 해답을 보고 진행하기로 하고 찾아봤는데 생각보다 심플한 해결책이 있었다.

 

1. 입력된 start_point, end_point를 오름차순으로 정렬

2. 두 번째 element부터 순회하되(s, e)

> case1 : s, e가 start_point와 end_point 사이에 있는 값이 들어오면 skip

> case 2 : s가 end_point보다 크면 더 이상 겹칠 수 있는 게 나오지 않으므로 길이 구해서(end_point - start_point) 누적하고 s, e를 start_point, end_point에 넣어줌

> case 3 : s가 start_point보다 작으면 그 값을 start_point에 넣어주고 e가 end_point보다 크면 그 값을 end_point에 넣어줌

3. 마지막의 길이 end_point - start_point를 누적해주고 출력

 

그림으로 아래와 같이 정리할 수 있다.

제출하다 몇 번 시간 초과가 났는데

case1에 대한 처리를 case 2처럼 해줬던 부분을 case1로 분리하고

start_point, end_point 모두 오름차순으로 정렬했더니 통과됐다.

 

작성한 소스는 아래와 같다.

from sys import stdin

if __name__ == "__main__":
    n = int(stdin.readline())
    res = 0
    ar = []
    for _ in range(n):
        ar.append(list(map(int, stdin.readline().split(' '))))
    ar.sort(key=lambda x : (x[0], x[1]))

    ma, mb = ar[0][0], ar[0][1]
    for i in range(1, n):
        a, b = ar[i][0], ar[i][1]
        if ma <= a and mb >= b:
            continue

        if mb < a:
            res += mb - ma
            ma = a
            mb = b
        else:
            ma = min(ma, a)
            mb = max(mb, b)

    res += mb - ma
    print(res)

매우 간단쓰한 문제였다고 보고(물론 개념 이해가 없었으면 어려웠겠지만)

비슷한 문제들을 계속 풀어서

다음에 이런 유형이 코딩 테스트에 나오면 고민 없이 바로 풀 수 있을 정도로 익숙해져야겠다.