문제 바로가기
문제:
매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자. 이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.
입력:
첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.
출력:
첫째 줄에 그은 선의 총 길이를 출력한다.
풀이 :
정답 3 프로에서 틀린 풀이
import sys
from collections import deque
n = int(input())
lst = deque(sorted([list(map(int,sys.stdin.readline().split(" "))) for _ in range(n)], key = lambda x:x[0]))
# 투포인터
left, right = lst.popleft()
lines = 0
while lst:
start, end = lst.popleft()
if start <= right:
lines += end - right
left = right
if start > right:
left = start
right = end
lines += end - start
print(lines)
(1,7) (2,5) 와 같은 상황을 고려 하지 못했다.
import sys
from collections import deque
n = int(input())
lst = deque(sorted([list(map(int,sys.stdin.readline().split(" "))) for _ in range(n)], key = lambda x:x[0]))
# 투포인터
left, right = lst.popleft()
lines = 0
while lst:
start, end = lst.popleft()
# 시작하는 선에 right 값이 다음 들어오는 끝값보다 크면 굳이 체크 x
# 즉 이미 있는 선 안에 겹치게 된다.
if right >= end:
continue
# 시작하는 선에 right 값이 다음 선 end 값과 사이에 있으면 right 값을 옮겨줘야함
# 즉 겹치는 선이면서 길이가 더 길어 진다.
elif start <= right < end:
right = end
else:
# 이어진 선 완성
lines += right - left
# 안 겹치는 새로운 선 만들
left = start
right = end
lines += right - left
print(lines)
다른 사람들 코드를 보면 튜플을 사용하는 경우도 있지만.
굳이 튜플 사용하지 않아도 통과된다.
내 아이디어는
왼쪽 좌표 값 기준으로 오름차순 정렬을 해준뒤
초기값인 left 와 right 를 세팅해 주었고.
그 다음값 을 돌면서
만약 다음 선의 end 값이 앞에 있는 right 값 보다 작으면 이미 속해 있다는 뜻이므로 continue 로 넘겨주고
다음 선의 시작 값이 이 전 선의 끝 값보다 작으면 이미 겹쳐져 있는 선이기 때문에
right 만 바꿔주면 된다.
다른 경우에는 선이 안 겹쳐지고 새로운 선을 만드는 것이기 때문에
새로운 선인 left 와 right 를 start 와 end로 바꿔주면 된다.
댓글