[백준 2473번 / java] 세 용액

문제

https://www.acmicpc.net/status?user_id=jeong52&problem_id=2473&from_mine=1

1. 산성 용액 : 1~1,000,000,000
2. 알칼리성 용액 : -1~-1,000,000,000
3. 양의 세 용액을 혼합한 용액 = 세 용액의 합
4. 세 용액을 혼합하여 특성값이 0에 가장 가깝게 만들어라.

 

풀이1

(바로 정답을 보려면 풀이2로 넘어가기)

 

용액의 합이 1억을 넘으므로, int가 아닌 long을 사용해야 한다.
3<=N<=5000이므로 완탐은 안 된다. 완탐할 경우 5000_C_3이므로 약 5000^3번의 연산이 필요하다.
-> 정렬 후 이분탐색..? 정렬 후 쓰리포인터?

 

start, end 포인터를 배열의 양 끝에 위치하게 한다.

합의 절댓값이 가장 작은 두  값을 선택한다.

선택된 두 값 제외한 나머지 값들 중에서, 셋의 합의  절댓값이 작은 값을 마저 선택한다.

그러나 이것은 잘못된 방법이다. 아래 설명을 참고하자.

코드 1

import java.io.*;
import java.util.*;

public class boj_2473 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        long[] t = new long[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            t[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(t);

        int start = 0;
        int end = N-1;
        long sum = Long.MAX_VALUE;
        String changedPointer = "";

        while(start < end){
            if(Math.abs(t[start] + t[end]) < Math.abs(sum)){
                sum = t[start] + t[end];
                if(start+1 == end)
                    break;
            }else{
                if(changedPointer.equals("end"))
                    end++;
                if(changedPointer.equals("start"))
                    start--;
                break;
            }

            if(Math.abs(t[start]) < Math.abs(t[end])){
                end--; changedPointer = "end";
            }else if(Math.abs(t[start]) > Math.abs(t[end])){
                start++; changedPointer = "start";
            }
        }

        long tmp = Long.MAX_VALUE;
        int thirdLiquid = 0;
        for(int i=0; i<N; i++){
            if(i == start || i == end)
                continue;
            if(Math.abs(sum + t[i]) < Math.abs(tmp)){
                tmp = sum + t[i];
                thirdLiquid = i;
            }
        }

        long[] ans = new long[3];
        ans[0] = t[start];
        ans[1] = t[end];
        ans[2] = t[thirdLiquid];

        Arrays.sort(ans);

        bw.write(ans[0] + " " + ans[1] + " " + ans[2]);
        bw.close();
    }
}

[반례]

6

8 -1 2 -10 10 7

출력 : -10 -1 10

정답 : -10 2 8

while(start < end){
            if(Math.abs(t[start] + t[end] + t[thirdOne]) < Math.abs(sum)){
                sum = t[start] + t[end] + t[thirdOne];
                if(start+1 == end)
                    break;
            }else{...
            }
            ...
        }

 

해당 코드에서 t[start] + t[end]가 현재까지 구해진 sum보다 작아야만 start, end를 움직여서 다음 경우를 확인할 수 있도록 하면 안 된다. start, end로 모든 경우를 따져봐야 한다.

 

반례처럼 만약 정렬된 수열의 양 끝이 -10, 10이 나와서 처음부터 가장 0에 가까운 숫자인 0이 나오면 다른 경우를 확인하지도 않고 -10, 10은 이미 정해져버린다. 그 상태에서 세 번째 용액을 찾아서 답으로 도출하게 된다. 

 

그러나 이 수열의 경우 -10, 2, 8이 정답이다.

t[start], t[end], t[thirdOne] 모두 찾아서 그 합의 최솟값을 구해야 한다.

 

풀이 2

쓰리 포인터를 사용한다.

• 배열을 오름차순으로 정렬한다.
  • 배열이 오름차순으로 정렬되어있어야 포인터를 앞 뒤로 움직이며 값의 합을 조절할 수 있다.
• 고정 포인터를 한 개 두고, 나머지 두 포인터를 옮겨가며 세 값의 합을 구한다.
  • 고정 포인터 'point'는 0부터 N-3까지로 둔다.
    • 반드시 고정 포인터 이후로 두 포인터가 위치하도록 해야 모든 경우의 수를 겹치지 않고 구할 수 있다.
  • 나머지 두 포인터는 'start', 'end'로, 현재 세 값의 합에 따라 둘 중 어떤 것을 움직일지 정한다.
    • 포인터의 초기값은 아래와 같이 둔다.
      • start = point+1
      • end = N-1
    • 세 값의 합이 양수 -> end--;
    • 세 값의 합이 음수 -> start++;
    • 이렇게 움직이는 이유는, 세 값의 합이 0에 가까워야 하기 때문이다.
    • 양수라면 더 작은 값을, 음수라면 더 큰 값을 더해주어야 합의 절댓값이 작아진다.

코드 2

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static long[] t;
    static int first, second, third;
    static long min = Long.MAX_VALUE, sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        t = new long[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            t[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(t);
        solve();

        bw.write(t[first] + " " + t[second] + " " + t[third]);
        bw.close();
    }
    static void solve() {
        for(int i=0; i<N-2; i++){
            int point = i;
            int start = i+1;
            int end = N-1;
            while(start < end){
                sum = t[point] + t[start] + t[end];
                if(Math.abs(sum) < Math.abs(min)){
                    min = sum;
                    first = point;
                    second = start;
                    third = end;
                }
                //sum<0이면 합의 절댓값을 줄이기 위해 양수가 늘어나야 하므로 start++
                if(sum < 0) start++;
                else end--;
            }
        }
    }
}

Note

• 쉽게 봤다가 큰코다친 문제이다.
• 알고리즘과 대략적인 로직을 떠올리기는 쉬웠지만, 반례가 많아 더 치밀하게 생각해야 했다.
  • #1
  • if(sum<0) start++; else end--; 즉, start와 end 포인터를 움직이는 부분을
    처음에는 if(Math.abs(t[start]) < Math.abs(t[end])) end--; else start; 로 작성했다.
  • 둘의 합이 0에 가까워야 하므로 둘 중 절댓값이 큰 것을 좀 더 0과 가깝게 만들어야 한다고 생각했기 때문이다.
  • 하지만 이것은 틀린 답을 도출한다.
  • start와 end의 절댓값이 작아지면 반드시 t[start]+t[end]의 절댓값이 작아지는 게 아니다!
  • 음수에 양수를 더하면 절댓값이 더 작아질 수 있다는 점도 생각해야 한다.
  • 예) 해당 조건문은 이 테스트케이스의 답을 -6, -2, 6으로 출력하게 한다. 하지만 정답은 -97 -2 98이다.
    

    5
    -2 6 -97 -6 98​

  • -97 -6 -2 6 98 와 같이 정렬된 상태에서 해당 조건문에 따라 start, end를 옮기면 -97 -2 98의 합을 시도해보지 않고 지나가기 때문이다. 
  • #2
  • 이미 Arrays.sort(t)로 원본 배열을 정렬한 상태에서 차례로 point, start, end를 뽑아 출력하므로, 답을 출력할 때 다시 한 번 정렬하지 않아도 된다.
• 꽤 많은 시간을 투자했지만 이번 문제를 통해 투포인터 알고리즘에 좀 더 익숙해진 것 같아 기쁘다.
• 오늘 스터디의 다른 문제 피드백에서 들었듯이, 이번 문제도 처음 짠 코드에서 코드 중복이 너무 많아보인다. 
• 적절한 분기와 모듈화를 통해 코드 중복을 피하자.