[백준 15922] 아우으 우아으이야!! - Python

문제 보기

[사용한 알고리즘]

구현

 

[문제 접근]

1. x, y 범위가 -10억 ~ 10억이고 입력 값의 개수가 최대 10만 개이기 때문에 O(n^2) 시간 복잡도로 구현하면 시간제한 2초를 초과합니다. 따라서 O(n) 시간 복잡도로 문제를 구현하고자 하였습니다.

2. x가 증가하는 순으로 좌표가 주어지기 때문에 기존에 주어진 좌표와 새로 들어온 좌표가 모두 겹치는 경우, x만 겹치는 경우, 둘 다 겹치지 않는 경우 3가지가 존재합니다. 따라서 각각의 경우에 따라서 기존의 좌표 값과 결괏값을 저장하는 변수를 관리하면 O(n) 시간 복잡도로 문제를 구현할 수 있다고 생각하였습니다.

 

[알고리즘]

1. 첫 번째 x, y 좌표를 입력받습니다.

2. 새로 들어온 temp_x, temp_y 좌표와 기존의 좌표의 포함 여부를 파악합니다.

 - temp_x, temp_y가 x, y 선분에 포함되면 다시 새로운 x, y 좌표를 입력받는다.

 - temp_x가 x, y 선분에 포함되고 temp_y가 x, y 선분에 포함되지 않으면 temp_y를 y값에 대입합니다.

 - temp_x와 temp_y 모두 x, y 선분에 포함되지 않으면 기존의 선분 길이를 result 변수에 저장하고 temp_x, temp_y 값을 x, y에 대입합니다.

3. result + (y - x)를 출력합니다.

 

[코드]

if __name__ == "__main__":
    n = int(input())
    x, y = map(int, input().split())
    result = 0

    for _ in range(n - 1):
        temp_x, temp_y = map(int, input().split())

        if x <= temp_y <= y:  # 포함
            continue
        elif x <= temp_x <= y and not x <= temp_y <= y:  # y 연장
            y = temp_y
        else:  # 새로운 선분
            result += y - x
            x, y = temp_x, temp_y

    print(result + (y - x))

 

+ 앞으로는 파이썬뿐만 아니라 자바를 이용해서도 알고리즘 공부를 수행할 예정입니다.