import sys
input = sys.stdin.readline
spots = []
for _ in range(int(input())):
s, e = map(int, input().split())
spots.append((s,e))
spots.sort(key= lambda x: x[0])
stack = []
for s, e in spots:
if not stack or stack[-1] < s:
stack.append(s)
stack.append(e)
else:
if stack[-1] < e:
stack.pop()
stack.append(e)
result = 0
for i in range(0, len(stack)-1, 2):
s, e = stack[i], stack[i+1]
result += abs(e-s)
print(result)
Hint
선의 길이를 재는 것이므로 시작점과 끝점만 알면 된다.
음수가 범위에 포함되어 있으니 이를 고려하는 걸 잊지 말자!!
풀이 과정
스택에는 시작점과 끝점을 기록한다. (A, B) (C, D) 이렇게 쌓음 -> 스택으로는 [A, B, C, D] 이렇게 쌓일 것이다.
스택이 비어있거나, top이 s 보다 작으면 이어지는 관계가 아니라 끊어진 선 관계이므로 stack에 (시작점, 끝점)을 추가한다.
top이 s보다 크면 이어진 선이 된다! -> e가 top보다 작으면 포함관계이므로 현재 stack을 유지하고, e가 더 크다면 더 길게 선을 그을 수 있게 되므로 top을 빼고 e를 새로운 끝점으로 넣는다
그리고 쌍 관계로 꺼내서 길이를 계산하면 된다.
'Algorithm > BaekJoon' 카테고리의 다른 글
[백준/Python] 2146번 - 다리 만들기 (0) | 2023.09.06 |
---|---|
[백준/Python] 2573번 - 빙산 (0) | 2023.09.06 |
[백준/Python] 1874번 - 스택 수열 (0) | 2023.09.02 |
[백준/Python] 2493번 - 탑 (0) | 2023.09.01 |
[백준/Python] 10828번 - 스택 (0) | 2023.09.01 |
import sys
input = sys.stdin.readline
spots = []
for _ in range(int(input())):
s, e = map(int, input().split())
spots.append((s,e))
spots.sort(key= lambda x: x[0])
stack = []
for s, e in spots:
if not stack or stack[-1] < s:
stack.append(s)
stack.append(e)
else:
if stack[-1] < e:
stack.pop()
stack.append(e)
result = 0
for i in range(0, len(stack)-1, 2):
s, e = stack[i], stack[i+1]
result += abs(e-s)
print(result)
Hint
선의 길이를 재는 것이므로 시작점과 끝점만 알면 된다.
음수가 범위에 포함되어 있으니 이를 고려하는 걸 잊지 말자!!
풀이 과정
스택에는 시작점과 끝점을 기록한다. (A, B) (C, D) 이렇게 쌓음 -> 스택으로는 [A, B, C, D] 이렇게 쌓일 것이다.
스택이 비어있거나, top이 s 보다 작으면 이어지는 관계가 아니라 끊어진 선 관계이므로 stack에 (시작점, 끝점)을 추가한다.
top이 s보다 크면 이어진 선이 된다! -> e가 top보다 작으면 포함관계이므로 현재 stack을 유지하고, e가 더 크다면 더 길게 선을 그을 수 있게 되므로 top을 빼고 e를 새로운 끝점으로 넣는다
그리고 쌍 관계로 꺼내서 길이를 계산하면 된다.
'Algorithm > BaekJoon' 카테고리의 다른 글
[백준/Python] 2146번 - 다리 만들기 (0) | 2023.09.06 |
---|---|
[백준/Python] 2573번 - 빙산 (0) | 2023.09.06 |
[백준/Python] 1874번 - 스택 수열 (0) | 2023.09.02 |
[백준/Python] 2493번 - 탑 (0) | 2023.09.01 |
[백준/Python] 10828번 - 스택 (0) | 2023.09.01 |