[python] 백준 2283 구간 자르기

https://www.acmicpc.net/problem/2283

2283번: 구간 자르기

 

문제 해결

• 리스트 인덱스를 x좌표로 하여 막대의 좌표 ( ex: (3,7)이면 vertical[3:7]에 +1씩 더해서 길이를 측정할 수 있도록 한다.)로 나타낸다.
• 원하는 만큼의 길이(k)가 안나오면 끝점(r)를 1씩 높여서 해당되는 길이만큼 증가시키고 그보다 크게 나오면 시작점(l)를 1씩 높여서 해당되는 길이만큼 줄이면서 원하는 값이 나오는지 측정한다.

 

CODE

import sys

n, k = map(int, input().split())
vertical = [0]*1000001

for _ in range(n):
    start, end = map(int, input().split())
    for i in range(start,end):
        vertical[i] += 1
l, r, val = 0, 0, 0
flag = False
while 0<=l<=r and r<1000001:
    if val==k:
        flag = True
        break
    elif val<k:
        val += vertical[r]
        r += 1
    else:
        val -= vertical[l]
        l += 1
if flag: print(l, r,sep=' ')
else:
    print(0, 0,sep=' ')