[백준] 알고리즘 분류(두 포인터,JAVA)2283번, 구간 자르기

문제 링크

2283번: 구간 자르기

 

---

 

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. B는 항상 A보다 큽니다.

2. A와 B를 잘랐을 때 남아있는 부분들의 길이의 합이 K가 되는 A와 B를 결과로 출력합니다.

3. A, B가 여러 개일 때 A가 가장 작은 경우를 결과로 출력합니다.

4. A도 가장 작은 값도 여러 개일 때 B가 가장 작은 값으로 결과를 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 누적합을 이용하여 각 구역의 선분을 개수를 구한 뒤 , 투 포인터로 탐색을 진행합니다.

 

3. 탐색이 끝난 뒤 조건에 만족하는 A와 B를 결과로 출력합니다.

 

 

누적합을 이용한 선분 개수 구하기!

 

아래와 같이 선분이 주어진다고 가정합니다.

아래 검은선 위치에서는 선분의 개수 : 1개

 

아래 검은선 위치에서는 선분의 개수 : 2개

 

아래 검은선 위치에서는 선분의 개수 : 3개

 

 

(선분의 시작 지점 + 1) ~ 선분의 끝나는 지점까지는 선분의 길이가 항상 1이 존재합니다.

 

※ 선분의 시작 지점은 포함되지 않는 것은 점이 시작되는 지점이지 선분이 늘어나있지 않기 때문입니다.

 

각 지점에서 선분의 시작이나 끝나는 지점이 존재할 때

 

선분의 시작 지점 + 1  : +1

 

선분의 끝나는 지점 : -1

 

반복하여 각 지점에 선분의 개수를 구합니다.

 

선분의 개수를 통해 누적합을 구해서 각 지점까지의 선분의 길이를 구합니다.

※예제입력을 설명하는 내용을 같이 보시면 이해하시기 편할 것입니다.

 

투 포인터를 이용해 A와 B를 구하기 위한 탐색!

 

각 지점에 대한 길이를 저장한 누적합을 구하였다면

 

최소값부터 투 포인터를 진행하여 탐색합니다.

 

예를 들어 아래와 같은 누적합과 K = 5일 때

 

0	1	6	9	15
start, end

 start - end = 0 < K

 

 

0	1	6	9	15
start		end

 start - end = 6 > K 

 

 

0	1	6	9	15
	start	end

 start - end = 5 : K == 5

A : 1, B : 6

 

3가지 경우 발견!

 

start - end < K

: end 증가!

 

start - end == 0: 조건 만족! A와 B 출력!

 

start - end > K: start 증가!

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

K : 25

 

선분 정보

 

2. 누적합을 이용하여 각 구역의 선분을 개수를 구한 뒤 , 투 포인터로 탐색을 진행합니다.

 

각 지점에 선분 개수

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	2	2	4	4	4	4	4	3	3	1	1	1	1	1

 

누적합

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	4	6	10	14	18	22	26	29	32	33	34	35	36	37

 

투 포인터 탐색!

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
s,e

s(start) : 0

e(start) : 0

e - s = 0 - 0 < K(25) : e 증가!

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
s	e

s(start) : 0

e(start) : 1

e - s = 1 - 0 < K(25)

 

 

....

 

 

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
		s							e

s(start) : 2

e(start) : 9

 

e - s = 29 - 4 == K(25)

 

A : 2

B : 9

 

3. 탐색이 끝난 뒤 조건에 만족하는 A와 B를 결과로 출력합니다.

 

A : 2

 

B : 9

 

※ 만약 A가 선분의 최소값이면 그 이전에서 잘라도 동일하기 때문에 A = 0이 됩니다.

※ A = 0이 되어야하는 것은 동일한 A B가 존재할 때 A가 낮은 것을 결과로 출력하기 때문입니다.

 

 

2 9을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용해서 선분에 대한 정보를 띄어쓰기 기준 나누었습니다.
• 각 지점의 선분 개수를 이용하여 누적합을 구합니다.
• 두 포인터를 이용하여 조건에 만족하는 A와 B를 구하기 위해 탐색합니다.
• 탐색이 끝난 뒤 구한 A와 B를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String args[]) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] count = new int[1000001];	//각 지점 선분 개수 저장 배열
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int max = -1, min = 1000001;	//선분 존재 최소, 최대값
        //선분에 대한 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," " );
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            count[left]++;	//선분 시작 : 선분 개수 증가!
            count[right]--;	//선분 끝 : 선분 개수 감소!
            //최대, 최소값 구하기
            min = Math.min(min, left);
            max = Math.max(max, right);
        }
        //누적합 구하기!
        for(int i=min+1;i<=max;i++)
            count[i] += count[i-1];

        //투 포인터 탐색
        int s_id = min, e_id = min;	//s_id : start, e_id : end
        int A = 0, B = 0;
        int s = 0;	//현재 값
        while(e_id <= max){
            if(s < K) {			//S + E < K
                s += count[e_id++];		//end 증가!
            }else if(s == K){	//S + E == K, 조건 달성!, 탐색 종료!
                A = s_id;	
                B = e_id;
                break;
            }else		//S + E > K
                s -= count[s_id++];		//start 증가
        }
        if(A == min)	//A가 최소값일 때 0으로 변경!
            A = 0;
        bw.write(A + " " + B);	//A와 B를 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}