[백준 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가 가장 작은 경우를 출력한다.

 

풀이과정

전형적인 투포인터 문제로 이해할 수 있었다.

투포인터 특성 자체가 특정 범위에서 조건을 만족 하는지 안하는지에 따라

범위가 넓어지느냐 좁아지느냐 인데 

위 문제도 K가 특정 구간의 합과 일치 할때 start와 end를 구하는 문제이기 때문에 쉽게 이해가 됐다.

위 문제에서 최악의 경우는 1천개의 수직선이 모두 0에서 1백만 까지의 범위를 갖는 경우이다.

이 때 1천개의 수직선을 모두 탐색한다면 총 10억개가 넘는 연산을 갖는다.

그러나 이 경우 N번만큼 연산을 줄일 수 있다.

 

1000000+1 만큼의 배열을 선언 후

input을 입력 받을때 마다 

시작위치+1 위치에서 +1을 하고 종료위치+1 에서 -1을 한다.

그 다음 처음부터 끝까지 arr[i]+=arr[i-1] 를 해주면

누적합을 구할 수 있다.

이렇게 하면 N번만큼 탐색하면서 풀 수 있다.

 

최종코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(){

    val solution = Solution()
    solution.solution()

}


internal class Solution {
    lateinit var arr: Array<Int>
    lateinit var br: BufferedReader
    var N: Int = 0
    var K: Int = 0

    fun solution() {
        arr = Array(1000002){0}
        br = BufferedReader(InputStreamReader(System.`in`))
        val NK = br.readLine().split(" ")
        N = NK[0].toInt()
        K = NK[1].toInt()

        for(i in 0..N-1){
            val input = br.readLine().split(" ")
            arr[input[0].toInt()+1]++
            arr[input[1].toInt()+1]--
        }
        for(i in 1..1000000){
            arr[i]+=arr[i-1]
        }

        var left = 0
        var right = 0
        var sum = 0
        while(true){
            if(sum<K){
                sum +=arr[++right]
            }else if(sum>K){
                sum -=arr[++left]
            }else{
                println("${left} ${right}")
                return
            }
            
            if(right==1000001) break

        }
        println("${0} ${0}")
    }
}

 

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

2283번: 구간 자르기