[240307] 알고리즘 리부트 26일차 - 백준 2295 자바

[Part1-Chapter07-Clip03]

- 백준 2295 세 수의 합

문제를 읽고 제일 먼저 두 수를 고정하고 집합의 원소인 set[k] 에서 나머지 한 수를 이분탐색하는 방식을 고민했다. 하지만 코드를 작성하다 먼길을 가버렸고 한참을 단순히 l과 r의 범위나 m을 추출하는 방식을 고치면 탐색의 범위를 조정할 수 있지 않을까라는 바보 같은 생각을 했다.

코드를 작성하면서 l과 r을 다시 의사코드로 작성해보니 l과 r이 아니라 첫수와 두수를 투 포인터 방식으로 고정하고 나머지 한개의 수를 다시 배열에서 이분탐색했어야 했는데 라는 깨달음과 다시 코드를 의도에 맞게 작성했다. 그런데 테스트 케이스도 모두 맞추는데 이상하게 3%에서 틀리는 것이다.... 

결국 다른 코드를 참고해보니 결국 내가 작성한 것은 모든 경우의 수를 고려하고 있지 않았다. 첫번째 수와 두번째 수를 투포인터 방식으로 지정한다면 확인하지 못하는 조합이 생기는 것이다.

즉, 문제에서는 세 개의 수가 모두 같을 수 있다고 하는데 투포인터를 써버리면 모든 두개의 수 조합을 추출하지 못한다. 예를 들면 0, 1 ,2의 인덱스가 있다고 할 때, 00,01,02,11,12, 22와 같은 조합이 가능한데 투 포인터로 구하면 경우에 따라 02, 12, 22 / 02, 01, 11 / 02, 01, 00만 추출하고 마는 것이다. 그리고 당연히 3%에서 틀릴 수밖에.. 따라서 두 개의 수 조합을 모두 구해서 합을 내어 배열 또는 리스트에 담아두고(이 때 이 자료구조를 정렬하는 것을 잊지말기) 정답 후보가 될 k번째 수를 기준으로 나머지 세번째 수 후보(set[0]~set[n-1])를 뺀 값과 두 개의 수의 조합이 일치하는 경우를 이분탐색으로 찾으면 문제를 해결할 수 있다.

package BaekJoon.binarysearch;

import java.util.*;

public class BJ2295_1 {
    public static int n;
    public static int[] set;

    public static void main(String[] args) {

        input();
        Arrays.sort(set);

        List<Integer> twoSum = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                twoSum.add(set[i] + set[j]);
            }
        }

        Collections.sort(twoSum);

        int ansIdx = 0;


        outer:
        for (int k = n - 1; k >= 0; k--) {
            for (int j = 0; j < n; j++) {

                int target = set[k] - set[j];

                int l = 0;
                int r = twoSum.size() - 1;

                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (twoSum.get(mid) == target) {
                        ansIdx = Math.max(k, ansIdx);
                        break outer;
                    } else if (twoSum.get(mid) > target) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }

            }
        }
        System.out.println(set[ansIdx]);


    }

    public static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        set = new int[n];

        for (int i = 0; i < n; i++) {
            set[i] = sc.nextInt();
        }
    }
}

아래는 투포인터 방식으로 잘못 풀이한 코드이다.

package BaekJoon.binarysearch;

import java.util.Arrays;
import java.util.Scanner;

public class BJ2295 {
    public static int n;
    public static int[] set;

    public static void main(String[] args) {

        input();
        Arrays.sort(set);

        int ansIdx = -1;

        outer:
        for (int k = n - 1; k >= 0; k--) {
            //System.out.println("k: " + k);

            // 투포인터
            int idxStart = 0;
            int idxEnd = k - 1;

            while (idxStart <= idxEnd) {

//                System.out.println("첫번째 수:" + set[idxStart]);
//                System.out.println("두번째 수:" + set[idxEnd]);

                int target = set[k] - set[idxEnd] - set[idxStart];

//                System.out.println("찾고자 하는 수:" + target);

                if (target > 0) {
                    int l = 0;
                    int r = n - 1;

                    while (l <= r) {
                        int mid = (l + r) / 2;

//                        System.out.println("l: " + l);
//                        System.out.println("mid: " + mid);
//                        System.out.println("r: " + r);

                        if (set[mid] == target) {
                            ansIdx = k;

//                            System.out.println("찾았음");
                            break outer;
                        } else if (set[mid] > target) {
                            r = mid - 1;
                        } else {
                            l = mid + 1;
                        }
                    }
                    idxStart++;
                    //System.out.println("못찾아서 시작 수 하나 키움");
                } else {
                    idxEnd--;
                    //System.out.println("숫자가 너무 커서 마지막 수 하나 줄임");
                }
            }
        }
        System.out.println(set[ansIdx]);
    }

    public static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        set = new int[n];

        for (int i = 0; i < n; i++) {
            set[i] = sc.nextInt();
        }
    }
}