[백준] 알고리즘 분류(두 포인터,JAVA)2473번, 세 용액

문제 링크

2473번: 세 용액

---

 

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 산성 용액, 알칼리 용액들을 3가지 섞어서 0에 가장 가깝도록 섞어야 합니다.

2. 용액에 대한 범위는 -10억 이상, 10억 이하입니다.

3. 0에 가장 가까운 세 용액의 특성값을 오름차순으로 정렬하여 결과로 출력합니다.

3. 0에 가장 가까운 경우가 중복될 경우 아무것이나 하나를 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 두 포인터를 이용하여 용액을 합치는 과정을 탐색합니다.

 

3. 0에 가장 가까운 경우의 세 용액의 특성값을 결과로 출력합니다.

 

 

0에 가장 가까운 세 용액 탐색!

 

세 용액의 특성값을 합쳤을 때 0에 가까운 값을  확인 : |용액1 특성값 + 용액2 특성값 + 용액3 특성값|

 

특성값은 임의의 순서로 주어져서 두 포인터르 사용하기 위해 오름차순으로 정렬을 해야합니다.

 

두 포인터를 진행하기 앞서 항상 사용되는 용액을 결정한 뒤

 

두 포인터를 이용하여 가장 큰 값과 가장 작은 값부터 비교하여 줄여나가면서 탐색합니다.

 

두 포인터 유의점!

 

앞서 항상 사용되는 용액을 설정하면

 

해당 용액보다 특성값이 작은 용액은 이전에 항상 사용되는 용액으로 설정되었기 때문에 중복된 탐색이 진행됩니다.

 

중복되는 것을 방지하기 위해 두 포인터를 진행되는 범위

 

항상 사용되는 용액 Idx + 1 ≤ n ≤ 용액의 개수

 

용액을 합쳣을 때 3가지 경우가 존재합니다.

 

용액1 특성값  + 용액2 특성값 + 용액3 특성값 < 0

 

: 0에 가까워지려면 고정된 값 제외한 특성값이 작은 값이 커져야 합니다.

 

용액1 특성값  + 용액2 특성값 + 용액3 특성값 = 0

 

: 이보다 좋은 특성값 존재 X, 현재 두 용액을 결과로 출력!

 

용액1 특성값  + 용액2 특성값 + 용액3 특성값 > 0

 

: 0에 가까워지려면 고정된 값 제외한 특성값이 큰 값이 작아져야 합니다.

 

 

예제입력 1.

 

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

 

N : 5

 

용액 정보

 

-2

6

-97

-6

98

 

2. 두 포인터를 이용하여 용액을 합치는 과정을 탐색합니다.

 

용액 특성값 오름차순 정렬!

 

-97

-6

-2

6

98

 

항상 사용할 용액 정하기!

 

가장 낮은 용액 -97을 항상 사용하기!

 

두 포인터 탐색 진행!

 

-97	-6	-2	6	98
고정	최소			최대

 

|고정 용액(-97) + 최소 용액(-6) + 최대 용액(98)| = 5

현재 가장 가까운 값 : 5

 

고정 용액(-97) + 최소 용액(-6) + 최대 용액(98) < 0

: 최소 용액 증가!

 

-97	-6	-2	6	98
고정		최소		최대

 

 

|고정 용액(-97) + 최소 용액(-2) + 최대 용액(98)| = 1

현재 가장 가까운 값 : 1

 

고정 용액(-97) + 최소 용액(-2) + 최대 용액(98) < 0

: 최소 용액 증가!

 

 

-97	-6	-2	6	98
고정			최소	최대

 

 

|고정 용액(-97) + 최소 용액(6) + 최대 용액(98)| = 7

현재 가장 가까운 값 : 1

 

고정 용액(-97) + 최소 용액(6) + 최대 용액(98) > 0

: 최대 용액 감소!

 

 

-97	-6	-2	6	98
고정			최소, 최대

 

최소 용액 == 최대 용액 : 현재 고정된 용액에서 가장 가까운 값 : 1 (-97, -1, 98)

 

이 방법으로 계속 탐색

 

....

 

3. 0에 가장 가까운 경우의 세 용액의 특성값을 결과로 출력합니다.

 

현재 가장 가까운 값 : 1( -97,  -2, 98)

 

-97 -2 98을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용해서 용액의 특성값을 띄어쓰기 기준 나누었습니다.
• 항상 사용되는 용액을 설정한뒤  두 포인터를 이용하여 최소와 최대를 지정하여 탐색합니다.
• 탐색을 진행할 때 세 용액의 절대값과 합에 따라 최소와 최대에 값들을 변경해줍니다.
• 탐색이 끝난 뒤 0에 가까운 세 용액의 특성값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 고정된 용액 기준 두 포인터를 탐색하여 0에 가장 가까운 용액들을 구합니다.

 

결과코드

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


class Main {
    static long answer = Long.MAX_VALUE;	//시작 최대값
    static int first, second, third, N;		//정답의 세 용액을 Idx가리키는 변수
    static boolean Flag = false;	//특성합이 0인 값 존재하는지 확인 변수
    static int[] arr;	//용액의 값 저장 배열
    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));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        arr  = new int[N];
        //용액 입력값 저장
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);	//용액 오름차순 정렬
        //각 고정된 용액 기준 두 포인터 탐색
        for(int i=0;i<=N-3;i++) {
            search(i);	//두 포인터 탐색
            if(Flag)		//특성합이 0인 세 용액 발견시.
                break;
        }

        //세 용액의 특성값 BufferedWriter 저장
        sb.append(arr[first]).append(" ").append(arr[second]).append(" ").append(arr[third]);
        bw.write(sb.toString());		//결과 출력
        bw.flush();
        bw.close();
        br.close();
    }
    //고정된 용액 기준 두 포인터로 특성합 0에 가장 가까운 값 찾는 함수
    static void search(int n){
        long value = arr[n];
        //두 포인터 범위 (고정된 용액Idx + 1 ≤ 범위 ≤ 최대 특성값 Idx) 
        int s = n+1, e = N-1;
        //두 포인터 탐색
        while(s < e){
            long temp = value + arr[s] + arr[e];
            if(Math.abs(temp) < answer){
                answer = Math.abs(temp);
                first = n;
                second = s;
                third = e;
            }
            if(temp > 0)	//용액1 특성값  + 용액2 특성값 + 용액3 특성값 > 0
                e--;	//큰 값 감소
            else if(temp == 0)	//용액1 특성값  + 용액2 특성값 + 용액3 특성값 = 0
                return;
            else		//용액1 특성값  + 용액2 특성값 + 용액3 특성값 < 0
                s++;	//작은 값 증가!
        }
    }
}