[백준, Java] 2230번, 수 고르기(투 포인터)

문제 링크

2230번: 수 고르기

---

 

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 수열 A[N]이 입력으로 주어집니다.

2. 수열에 두 수의 차가 M 이상이면 제일 작은 경우를 결과로 출력합니다.

3. 두 수를 고를 때 같은 수를 선택할 수 있습니다.

 

알고리즘 진행 순서.

 

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

 

2. 투 포인터를 이용해서 M 이상인 제일 작은 차이를 탐색합니다.

 

3. 탐색을 통해 구한 제일 작은 차이를 결과로 출력합니다.

 

 

제일 작은 차이 탐색

 

투 포인터를 이용하기 위해서 주어진 수열을 오름차순 정렬합니다.

 

투 포인터를 처음 진행할 때

 

start : 0(index)

 

end : 0(index)

 

시작합니다.

 

※ 같은 수를 선택할 수 있기 때문에 같은 인덱스에서 시작합니다.

 

 

투 포인터 진행할 때 3가지 경우

 

두 수의 차이 : Dif

 

Dif > M : 차이가 M보다 커서 더 작은 값을 찾아야 하기 때문에 start + 1

 

Dif == M : M보다 작은 차이가 존재할 수 없기 때문에 제일 작은 차이는 M이 됩니다.

 

Dif < M : 차이가 M보다 작아서 더 큰 값을 찾아야 하기 때문에 end + 1

 

예제입력 1.

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

N : 3

 

M : 3

 

1

5

3

 

2. 투 포인터를 이용해서 M 이상인 제일 작은 차이를 탐색합니다.

 

투 포인터를 하기 위해서 정렬을 진행합니다.

 

1

3

5

 

투 포인터 진행

 

Start : 0

 

End : 0

 

1	3	5
Start, End

 

차이 : End(1) - Start(1) = 0

 

→ Dif(0) < M : End + 1

 

Start : 0

 

End : 1

 

1	3	5
Start	End

 

차이 : End(3) - Start(1) = 2

 

→ Dif(2) < M : End + 1

 

Start : 0

 

End : 2

 

1	3	5
Start		End

 

차이 : End(5) - Start(1) = 4

 

→ Dif(4) > M : Start + 1

 

Start : 1

 

End : 2

 

1	3	5
	Start	End

 

 

차이 : End(5) - Start(3) = 2

 

→ Dif(2) < M : End + 1

 

Start : 1

End : 3

 

더 이상 투 포인터를 진행할 수 없으므로 탐색 종료!

→ End의 인덱스가 범위를 벗어났습니다.

 

3. 탐색을 통해 구한 제일 작은 차이를 결과로 출력합니다.

 

 

 

M이상인 제일 작은 차이 : 4(1, 5)

 

4을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 수열 정보를 저장합니다.
• 투 포인터를 진행하기 위해 Collections.sort()을 이용해서 오름차순 정렬을 진행합니다.
• 투 포인터의 3가지 경우를 비교해서 M 이상인 제일 작은 차이를 탐색합니다.
• 탐색이 끝난 뒤 제일 작은 차이를 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.ArrayList;
import java.util.Collections;
import java.util.List;
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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        //수열의 값 저장 리스트
        List<Integer> values = new ArrayList<>();
        //수열의 값 저장
        for(int i=0;i<N;i++)
            values.add(Integer.parseInt(br.readLine()));
        Collections.sort(values);	//투 포인터를 위한 내림차순 정렬
        //투 포인터 인덱스 초기화
        int start = 0;
        int end = 0;
        int result = Integer.MAX_VALUE;
        //투 포인터 진행
        while(end < N){
            //차이 구하기
            int dif = values.get(end) - values.get(start);
            //M 이상이면서 제일 작은 차이인지 확인
            if(dif >= M && dif < result)
                result = dif;
            //Dif == M일 때
            if(result == M)
                break;
            if(dif <= M)	//Dif < M
                end++;
            else		/Dif > M
                start++;
        }
        //제일 작은 값 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();


    }
}