[백준 2473번] 세 용액 (Java 풀이)

백준알고리즘 2473번 : 세 용액 (Solved.ac 난이도 Gold4)

 

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

2473번: 세 용액

 

 

숫자 3개를 선택하여 가장 절대값이 가장 작은 숫자를 만드는 조합을 출력하는 문제이다.

두개라면 two pointer를 사용하여 풀 수 있을꺼라 생각하였는데,

고민하다가 하나를 고정하는 대신 나머지 2개를 투 포인터로 fix하는 방법은 어떨까 생각해보았다.

물론 내가 작성한 logic은 중복으로 탐색하는 경우가 충분히 발생할수 있다.


숫자 하나를 fix하는 것을 제외하고는 투 포인터와 다르지 않다.

다만 fix하는 숫자의 위치를 for문을 한번 돌면서 바꿔줄 것이기 때문에,

각 포인터들은 fix하는 숫자가 있는 index는 타지 않도록 충분한 조건을 걸어주었다.

당연하지만, 이렇게 해야 fix하는 숫자와 포인터 2개로 총 3개의 서로 다른 숫자를 뽑아줄 수 있다.

 

 

풀이 과정

---

1. 숫자를 배열으로 받은 뒤 오름차순으로 정렬한다.

2. 첫번째 index와 마지막 index가 모두 양수거나 모두 음수인 case는 0,1,2 혹은
    arr.length-3,-2,-1을 출력해주면 되므로 if문으로 배제해준다.

3. 2번의 case가 아닌경우, two pointer를 사용한다.
3-1. for문을 돌면서 고정할 숫자를 지정해주며,
      포인터들은 고정 숫자의 index를 피하면서 돌 수 있도록 조건문을 설정해준다.
3-2. fix값을 포함한 투 포인터 값의 합의 절대값이 기존 절대값보다 작다면, 숫자 조합을 바꿔준다.
3-3. 최종적으로 남은 숫자 목록을 오름차순으로 출력한다.

 

 

소스 ▽

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main { // [Gold4] 2473번 : 세 용액
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        long[] arr = new long[num];
        for (int i = 0; i < num; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);
        long min = 3000000001L;
        long fix = 0;
        long ans[] = new long[3];
        if (arr[0] * arr[arr.length - 1] > 0) {//좌우 모두 음수일때/좌우 모두 양수일때 -> 앞 if문에서 제거
            if (arr[0] > 0) {
                System.out.println(arr[0] + " " +arr[1]+ " " + arr[2]);
            } else {
                System.out.println(arr[arr.length - 3]+ " " + arr[arr.length - 2]+ " " + arr[arr.length - 1]);
            }
        } else {//좌측끝은 음수, 우측 끝은 양수일때
            stop:
            for (int i = 0; i < num; i++) {
                fix = arr[i];
                int x = i != 0 ? 0 : 1;
                int y = i == num - 1 ? num - 2 : num - 1;
                while (x < num && y >= 0 && x < y) {
                    if (Math.abs(arr[x] + arr[y] + fix) < Math.abs(min)) {
                        min = arr[x] + arr[y] + fix;
                        ans[0] = fix;
                        ans[1] = arr[x];
                        ans[2] = arr[y];
                    }
                    if (arr[x] + arr[y] + fix > 0) {
                        y--;
                        if (y == i) {
                            y--;
                        }
                    } else if (arr[x] + arr[y] + fix < 0) {
                        x++;
                        if (x == i) {
                            x++;
                        }
                    } else {
                        break stop;
                    }
                }
            }
            Arrays.sort(ans);
            for (int i = 0; i < 3; i++) {
                System.out.print(ans[i] + " ");
            }
        }

    }
}