[백준] 단계별로 풀어보기(단계:26, 투 포인터,JAVA)2470번, 두 용액

문제 링크

2470번: 두 용액

---

주의사항

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

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

---

문제 설명

---

접근 방법

투 포인터는 두 가지의 위치를 가리키는 포인터 Start, End를 이용하여 1차원 배열에 저장된 값들에 범위를 더하여 해당하는 값을 구하거나 포인터가 가리키는 값을 더해서 원하는 값을 구할 수 있도록 하는 알고리즘입니다.

 

투 포인터를 사용할 때에는 주로 정렬한 상태에서 사용합니다.

 

이 문제에 핵심은

1. N개의 용액 중 2개의 용액의 특성합이 0에 가장 근접한 각 용액의 특성을 출력해야한다.

2. 용액을 합칠 때 같은 용액끼리 합쳐도 상관없다.

3. 가장 가까운 용액을 만들어내는 경우가 다수인 경우 아무거나 하나를 출력한다.

4. 특성값은 모두 다르다.

 

투 포인터 알고리즘에서는 위치를 가리키는 2가지 포인터를 설정하였습니다.

Start = 0

End = 배열의 크기 - 1

 

이후 저는 특성합을 오름차순으로 정렬한 뒤에 아래에 규칙대로 탐색하였습니다.

1. start의 값 + end의 값 > 0 : end - 1

2. start의 값 + end의 값 = 0 : 탐색 종료

3. start의 값 + end의 값 < 0 : start + 1

 

위 규칙이 나온 이유는

만약 start의 값 + end의 값이 양수일 때 0과 더 가까워지려면 큰 값이 더 작아져야 합니다.

 

N개의 특성합을 오름차순으로 정렬하였기 때문에 end의 값이 큰 값을 가리키기 때문에

 

end - 1을 해주는 것입니다.

 

start의 값 + end의 값이 음수이면 0과 가까워지려면 작은 값이 커져야 합니다.

 

오름차순 정렬로 start의 값이 작은 값을 가리키기 때문에 start + 1을 해줍니다.

 

start의 값 + end의 값이 0이면 더 이상 0에 근접한 값이 없기 때문에 탐색을  종료합니다.

 

예제입력 1을 오름차순으로 정렬한 뒤 표로 표현하면

N : 5, 현재 0의 가장 근접한 값 : INF

근접한 값을 처리할 때에는 절대값을 이용하여 가까운 값을 비교합니다.

-99	-2	-1	4	98
Start				End

Start(-99) + End(98) = 1(1>0)

|1| < INF  = 1

규칙1 적용 → End - 1

 

N : 5, 현재 0의 가장 근접한 값 : 1

-99	-2	-1	4	98
Start			End

 

Start(-99) + End(4) = -95(-95<0)

|-95| > 1 = 1

규칙 3 적용 → Start + 1

 

N : 5, 현재 0의 가장 근접한 값 : 1

-99	-2	-1	4	98
	Start		End

 

Start(-2) + End(4) = 2(2>0)

|2| > 1 = 1

규칙 1 적용 → End - 1

 

N : 5, 현재 0의 가장 근접한 값 : 1

-99	-2	-1	4	98
	Start	End

Start(-1) + End(4) = 3(3>0)

|3| > 1 = 1

규칙 1 적용 → End - 1

 

N : 5, 현재 0의 가장 근접한 값 : 1

-99	-2	-1	4	98
	Start, End

탐색 종료!

 

0의 가장 근접한 값이었던 1일 때 Start와 End 값을 결과로 출력합니다.

Start = -99, End = 98

결과로 -99 98이 출력됩니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값(N, 용액의 특성합)를 저장합니다.

2. 특성합을 오름차순으로 정렬합니다.

3. 위 규칙을 적용합니다. 

4. 0과 가까운 Start, End를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 용액에 특성합을 분리하였습니다.
• 규칙을 적용하여 0에 가장 가까운 합을 가지는 두 용액을 구하는 cal함수를 만들었습니다.
• BufferedWriter에 0에 가장 가까운 합을 가지는 두 용액을 오름차순으로 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 투 포인터 알고리즘을 통해 Start, End를 이용해서 경우의 수를 구하였습니다.
• cal은 반복문을 통해 위 규칙을 적용하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	static int[] num;	//용액 특성합 저장 배열
	static int startResult, endResult;	//0과 가까운 Start,End 값 저장 변수
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----------입력값 저장 및 배열 초기화---------
    	int N =Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	num = new int[N];
    	for(int i=0;i<N;i++)
    		num[i] = Integer.parseInt(st.nextToken());
    	Arrays.sort(num);		//특성합 오름차순 정렬
    	cal(N);		//0에 가까운 Start,End 구하는 함수
    	bw.write(num[startResult] + " " + num[endResult] + "\n");
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //----------0에 가까운 Start, End 구하는 투 포인터 함수---------
    static void cal(int n) {
    	int start = 0;		//Start 포인터
    	int end = n-1;		//End 포인터
    	int result = Integer.MAX_VALUE;		//현재 0에 가까운 값
    	while(start<end) {
    		int temp = num[start] + num[end];
    		if(temp == 0) {		//규칙 2.
    			startResult = start;
    			endResult = end;
    			return;
    		}
    		if(result > Math.abs(temp)) {	//현재 0에 가까운 값보다 작은 가까운 값일 때
    			result = Math.abs(temp);
    			startResult = start;
    			endResult = end;
    		}

    		if(temp > 0)	//규칙1.
    			end--;
    		else		//규칙2.
    			start++;
    	}
    	return;
    }
}