문제 링크

성능 요약

메모리: 55612 KB, 시간: 316 ms

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 중간에서 만나기

제출 일자

2025년 1월 9일 11:38:58

문제 설명

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번째 수를 출력하면 된다.

풀이

느낀점

• 스터디에서 모의코테로 풀어보았다.
• 완탐은 무조건 시간초과인걸 아는데 효율적인 방법이 생각나지 않아서 나중에 풀이를 참고했다.
• 참고한 풀이에서는 두 수를 더한 값들을 List에 저장하고 binarySearch로 값의 존재여부를 판단했는데, 나는 HashSet을 사용했다.

설계 : 총 40분

• nums[x] + nums[y] 로 만들어진 수들을 저장해두고 nums[k] - nums[z]를 순회하며 같은 수가 있는지 판단한다.
• List의 contains는 O(N), binarySearch는 O(logN), HashSet의 contains는 O(1)이기 때문에 수 저장에 HashSet을 사용한다.
• Set 자료구조를 사용하면 중복된 수도 하나로 처리하기 때문에 메모리 측면에서도 더 효율적이다.

코드(Java)

• 구현 시간: 10분

package 코테_boj_2295_세수의합;

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 코테_boj_2295_세수의합
 * Date: 2025.01.09
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int[] nums;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int 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);
		
		Set<Integer> sum = new HashSet<>();
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) sum.add(nums[x] + nums[y]);
		}
		
		out: for (int k = n-1; k >= 0; k--) {
			for (int z = 0; z < n; z++) {
				if (sum.contains(nums[k] - nums[z])) {
					bw.write(String.valueOf(nums[k]));
					break out;
				}
			}
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

참고한 풀이

설계에 대해 이해한 내용

• 입력받은 n개의 수 배열을 nums = new int[n] 라고 할때, num[x] + num[y] + num[z] = num[k] 인 num[k] 중 가장 큰 수를 구하는 문제이다. (단, x, y, z, k는 서로 같을 수 있다.)
• 세 수의 합을 순회하는 것은 4중 for문으로 완전탐색 시 시간초과가 예상된다. (세 수 덧셈(N^3) 및 결과 탐색(N))
• nums[x] + nums[y] = nums[k] - nums[z] 로 바꾸어 생각해볼 수 있다.
• nums[x] + nums[y] 로 만들어진 수들을 저장해두고 nums[k] - nums[z]를 순회하며 같은 수가 있는지 판단한다.
• 이때, 저장된 수에서 단순 순회를 통해 해당하는 값을 찾으려면 위 4중 for문과 차이가 없다.
• 저장된 수를 정렬하여 이분탐색하면 더 빠르게 해당하는 수의 존재 여부를 알 수 있다.

코드(Java)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        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();
        List<Integer> sum = new ArrayList<>();
        for (int i = 0 ; i < N ; i++){
            for (int j = 0 ; j < N; j++){
                sum.add(arr[i] + arr[j]);
            }
        }
        Arrays.sort(arr);
        Collections.sort(sum);

        for (int i = N-1; i>=0; i--){
            for (int j = N-1; j>=0; j--){
                int minus = arr[i] - arr[j];

                if (Collections.binarySearch(sum,minus)>=0){
                    System.out.println(arr[i]);
                    return;
                }
            }
        }
    }
}

참고한 풀이 출처: https://kimtaesoo99.tistory.com/149