[코딩테스트] [2295] 세 수의 합

[2295] 세 수의 합

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

16397

5042

3357

28.500%

문제

N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.

예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경우만 입력으로 주어진다.

출력

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최대가 되도록 하는 것이 목적이다. x, y, z, k가 서로 같아도 된다. 이때, k번째 수를 출력하면 된다.

문제풀이

이 문제는 이분탐색방법으로 풀 수 있다.

일단 어떤 값을 찾을 것인지 생각해보자. 세 수를 더해서 나온 수 중 가장 큰 값을 찾는 문제이다.

x + y + z = k 이다. 만약 z를 이항하게 되면 x + y = k - z 이다.

위의 공식을 이용하여 이분 탐색 방법으로 찾아보자.

그렇다면 (x+y) 즉 더한 값들을 저장한 배열을 만들고 그 값들을 k-z 와 같은 지 찾아보자.

0. 입력받기

N개만큼 입력을 받기에 N개의 크기를 갖고 있는 arr배열을 생성해주자.

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();

1. 이분탐색방법 함수 만들기

이분탐색방법으로 배열안에 값이 있는지 찾아주는 함수를 만들자.

    static boolean isExist(int[] arr, int x) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] < x) l = m + 1;
            else if (arr[m] > x) r = m - 1;
            else return true;
        }
        return false;
    }

2. x+y 값을 갖고 있는 배열을 만들자.

이때 sums 배열의 크기는 N * (N + 1) / 2 이다.

그 이유는 arr[i] + arr[j]를 하려면 아래와 같이 더해줘야하기에 조합의 총 수는 N * (N + 1) / 2 이다.

arr[0] + arr[0] arr[0] + arr[1] arr[0] + arr[2] ... arr[N-1] + arr[N-1] 첫 번째 요소가 arr[0]일 때, 두 번째 요소는 N개 중 N개를 선택 첫 번째 요소가 arr[1]일 때, 두 번째 요소는 N-1개를 선택 ... 첫 번째 요소가 arr[N-1]일 때, 두 번째 요소는 1개를 선택

        int[] sums = new int[N * (N + 1) / 2];
        int sumIndex = 0;
        for (int i = 0; i < N; i++)
            for (int j = i; j < N; j++)
                sums[sumIndex++] = arr[i] + arr[j];

3. x+y == k-z 값을 찾아보자.

이분탐색방법을 사용하려면 정렬을 해줘야 한다.

오름 차순으로 정렬 후 arr[i] - arr[j] 값이 sums배열안에 있는지 확인해주자.

혹시 모든 값이 0이 일수도 있으니 ans -1로 두어 0도 문제없이 나오게 해

        Arrays.sort(sums);

        int ans = -1;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                int target = arr[i] - arr[j];
                if (isExist(sums, target))
                    ans = Math.max(ans, arr[i]);
            }
        System.out.println(ans);

시간복잡도

이 알고리즘의 시간복잡도는 입력 받을 때 O(N), sums 배열 생성할때 O(N^2), Sums 배열 정렬할때 O(N^2 * log N), x+y == k-z 값을 찾을 때 O(N^2logN)이다. 즉, O(N^2 log N)

Set을 이용한 풀이

Set 자료구조를 이용하여 문제를 풀어보자.

0. 입력받기

마찬가지로 입력을 받아주자.

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();

1. Set을 이용한 sums 만들기.

arr[i] + arr[j]를 더한 값이 중복이 될 수 있기에 Set을 사용해서 중복된 값 중 하나만 들어오게 한다.

        Set<Integer> sums = new HashSet<>();
        for (int i = 0; i < N; i++)
            for (int j = i; j < N; j++)
                sums.add(arr[i] + arr[j]);

2. k-z값이 sums에 있는지 확인하기

set의 contains 메소드를 사용하여 값이 있다면 그 값을 출력하게 하자 훨씬 간단하게 코드를 작성할 수 있다.

        int ans = -1;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                int target = arr[i] - arr[j];
                if (sums.contains(target))
                    ans = Math.max(ans, arr[i]);
            }

시간복잡도

이 알고리즘의 시간복잡도는 입력 받을 때 O(N), sums 배열 생성할때 O(N^2),

k-z값이 sums에 있는지 확인할 때 O(N^2)이다 즉 O(N^2)이다.

결론

1. 첫 번째 알고리즘 (이진 탐색을 사용한 방법) 시간 복잡도: O(N² log N) 배열의 모든 쌍의 합을 계산하고 정렬한 후, 각 요소에 대해 이진 탐색을 수행한다.
2. 두 번째 알고리즘 (해시셋을 사용한 방법) 시간 복잡도: O(N²) 모든 쌍의 합을 해시셋에 저장하고, 각 요소에 대해 해시셋에서 존재 여부를 확인한다.

즉, 시간이 두 번째 알고리즘이 빠르다 시간 문제 시간을 비교를 해보면 2번째가 더 빠르다는 것을 알 수 있다.

 

위: Set풀이 아래: 이분탐색풀이