백준 2295 세 수의 합

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/2295

2. 코드가 나오기까지 🛠️

(1) 시간복잡도 분석 ⏳

• 모든 두 수의 합 더하기 = $$O(N^{2})$$

• 모든 두 수의 뺄셈 확인 = $$\text{최악의 경우: }$$O$$(N^{2})$$

3. 코드 🌐

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



public class Main {
    static int N;
    static int [] nums;
    static HashMap<Integer, Boolean> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nums = new int [N];
        for(int i = 0; i < N; i++){
            nums[i] = Integer.parseInt(br.readLine());
        }        Arrays.sort(nums);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                map.put(nums[i]+nums[j], true);
            }        }
        for(int i = N-1; i >= 0; i--){
            for(int c = 0; c < N; c++){
                if(map.getOrDefault(nums[i] - nums[c], false)){
                    System.out.println(nums[i]);
                    return;
                }
            }
        }
    }
}

4. 트러블 슈팅 or 배운 점📝

(1) 투 포인터 + 이분 탐색으로는 풀리지 않을까?

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



public class Main {
    static int N;
    static int [] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nums = new int [N];
        for(int i = 0; i < N; i++){
            nums[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(nums);

        for(int i = N-1; i >= 3; i--){
            if (isComplete(i)) {
                System.out.println(nums[i]);
                return;
            }
        }
    }
    public static boolean isComplete(int target){
        int left = 0;
        int right = target-1;
        while (left <= right){
            int result = binary_search(target,left,right);
            if(result == 0) return true;
            else if(result == -1) right--;
            else left++;
        }
        return false;
    }

    public static int binary_search(int target, int left, int right){
        int start = left;
        int end = right;
        while (start <= end){
            int mid = (start+end)/2;
            if(nums[left] + nums[right] + nums[mid] == nums[target]) return 0;
            else if(nums[left] + nums[right] + nums[mid] > nums[target]) end = mid - 1;
            else start = mid+1;
        }
        if(end <= left) return -1;
        else return 1;
    }
}

5
1
2
12
17
25