[백준] 2295번 - 세 수의 합 [Java][C++]

문제 링크

---

1. 문제 풀이

자연수들로 이루어진 집합 $U$ 에서 고른 세 수의 합이 $U$ 에 포함되는 가장 큰 수를 찾는 문제다. $N$ 이 최대 $1,000$ 이어서 3중 반복문을 통한 풀이는 시간 초과가 발생하게 되는데 이를 2중 반복문 두 개로 쪼개서 해결하는 중간에서 만나기를 적용해야 한다. 핵심은 $a + b + c = d$ 를 만족하는 $d$ 를 찾을 때, $a + b = d - c$ 로 찾는 것이다. 이분 탐색을 활용한 방법과 집합을 활용한 방법 두 가지로 해결했다.

---

2. 코드

1. 이분 탐색 [Java]

이분 탐색의 경우 먼저 $U$ 을 통해 $a + b$ 를 2중 for문으로 계산하여 배열에 저장한 후 정렬한다. 이후 다시 2중 for문을 돌며 $d - c$ 가 해당 배열에 존재하는지 판단하는 방식으로 2번의 2중 for문으로 찾았고, 순회도 역순으로 해서 찾는 순간 바로 탐색을 종료하도록 구현했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);  // 역순 조회로 d를 발견하면 종료하기 위해 정렬

        int[] sumArr = new int[N * (N + 1) / 2];
        int idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                sumArr[idx++] = arr[i] + arr[j];
            }
        }
        Arrays.sort(sumArr);  // 이분 탐색을 위해 정렬

        // a + b + c = d -> a + b = d - c
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (Arrays.binarySearch(sumArr, arr[i] - arr[j]) >= 0) {
                    System.out.println(arr[i]);
                    return;
                }
            }
        }
    }
}

2. 해시를 사용한 집합과 맵 [Java]

HashSet 도 유사한데 $a + b$ 의 결과를 저장한 해시셋을 만들고 $d - c$ 가 해시셋에 존재하는지 여부로 찾으면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);  // 역순 조회로 d를 발견하면 종료하기 위해 정렬

        // a + b 미리 저장
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                set.add(arr[i] + arr[j]);
            }
        }

        // a + b + c = d -> a + b = d - c
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (set.contains(arr[i] - arr[j])) {
                    System.out.println(arr[i]);
                    return;
                }
            }
        }
    }
}

3. 이분 탐색 [C++]

이분 탐색의 경우 먼저 $U$ 을 통해 $a + b$ 를 2중 for문으로 계산하여 벡터에 저장한 후 정렬한다. 이후 다시 2중 for문을 돌며 $d - c$ 가 해당 벡터에 존재하는지 판단하는 방식으로 2번의 2중 for문으로 찾았고, 순회도 역순으로 해서 찾는 순간 바로 탐색을 종료하도록 구현했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;
    sort(v.begin(), v.end());  // 역순 조회로 d를 발견하면 종료하기 위해 정렬

    vector<int> sumArr;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            sumArr.push_back(v[i] + v[j]);
        }
    }
    sort(sumArr.begin(), sumArr.end());  // 이분 탐색을 위해 정렬

    // a + b + c = d -> a + b = d - c
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if (binary_search(sumArr.begin(), sumArr.end(), v[i] - v[j])) {
                cout << v[i];
                return 0;
            }
        }
    }
}

4. 해시를 사용한 집합과 맵 [C++]

unordered_set 도 유사한데 $a + b$ 의 결과를 저장한 해시셋을 만들고 $d - c$ 가 해시셋에 존재하는지 여부로 찾으면 된다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;
    sort(v.begin(), v.end());  // 역순 조회로 d를 발견하면 종료하기 위해 정렬

    // a + b 미리 저장
    unordered_set<int> st;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            st.insert(v[i] + v[j]);
        }
    }

    // a + b + c = d -> a + b = d - c
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if (st.count(v[i] - v[j])) {
                cout << v[i];
                return 0;
            }
        }
    }
}

---

3. 풀이 정보

1. 이분 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	252 ms	20316 KB	1097 B

2. 해시를 사용한 집합과 맵 [Java]

언어	시간	메모리	코드 길이
Java 11	288 ms	47364 KB	1011 B

3. 이분 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	28 ms	5228 KB	802 B

4. 해시를 사용한 집합과 맵 [C++]

언어	시간	메모리	코드 길이
C++ 17	192 ms	23312 KB	715 B

---