⭐⭐⭐⭐[백준] [파이썬] [투 포인터] 2283번: 구간 자르기

 

투 포인터 문제집 : https://www.acmicpc.net/workbook/view/8709

 

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

 

문제

수직선(數直線) 상에 구간 N개가 있다. 임의의 두 정수 A, B(A < B)를 정하여, 각 구간에서 A와 B 사이에 포함되지 않은 부분을 모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.

입력

1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다.

2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다.

출력

두 정수 A, B를 출력한다. 조건을 만족하는 A, B가 존재하지 않으면 “0 0”을 출력한다.

조건을 만족하는 A, B가 여러 개 존재할 때는 A가 가장 작은 경우를 출력한다. 그것도 여러 개 존재할 때는 B가 가장 작은 경우를 출력한다.

예제 입력 1 

4 25
0 10
3 15
0 8
3 10

예제 출력 1 

2 9

---

 

문제 요약:

각 구간에서 A와 B 사이에 포함되지 않은 부분을 모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.

-> 구간 A와 B 사이의 겹치는 구간의 누적합을 구하여랴!!

 

아니 왜 문장을 이렇게 어렵게 쓰는거야~~

 

단순히 보면 그냥, 선들 겹치는 부분 누적합을 구하라는 뜻이다. 그 누적합이 K가 되도록 하는 구간 A와 B를 구하라는 말.

 

나는 처음에 A와 B 사이에 포함되지 않는 부분의 누적합인 줄 알았잖아!!

 

그러면 아주 전형적이고 대표적인 투포인터 문제이며 

겹치는 구간을 미리 더해준 arr를 먼저 고려하여 만들어준 후 투 포인터를 진행하면 되겠다. 

 

if __name__=="__main__":
    N,K = map(int, input().split())
    max_num = 1_000_000 + 1
    array = [0]*max_num
    for _ in range(N):
        start,end = map(int, input().split())
		# 선의 위치 겹치는 부분은 += 1씩 증가한다. 
        for i in range(start, end):
            array[i] += 1
        
    flag = False
    left, right = 0,0
    add = 0
    
    while left<=right<max_num:
        if add == K:                # 나머지 누적합이 목표값이 되었을 때
            flag = True
            break
        elif add < K:
            add += array[right]		# 오른쪽 화살표 오른쪽으로 이동 
            right += 1
        elif add > K:
            add -= array[left]		# 왼쪽화살표 오른쪽으로 이동  
            left += 1 
    
    if flag:
        print(*[left, right])
    else:
        print(*[0,0])