[JAVA]BOJ 2295, 세 수의 합

생각해야 할 게 많았다..

시간복잡도에서 N의 범위가 1000까지라서 그냥 이진탐색하면 되겠지~ 했는데 반복문 안에서 이진탐색을 하니 시간초과가 일어나더라. 그래서 음.. 어떻게 하는거지 하고 검색했더니 HashSet을 이용한 문제였다.

 

Set은 중복된 요소를 허용하지 않는 컬렉션을 정의하는 인터페이스다. 쉽게말해 중복을 허용하지 않는다. 종류로는 HashSet, LinkedHashSet, TreeSet이 있고 HashSet만 순서를 유지하지 않는다. 이 문제에서는 순서를 따지지 않기때문에 HashSet을 이용했다.

 

문제의 큰 흐름은 이렇다.

 

1. U집합 입력받고 정렬하기

2. U집합의 두 개의 합 Set으로 저장하기

3. Set과 U집합을 이용해 세 수의 합 최댓값 구하기

 

1. U집합 입력받고 정렬하기

배열로 받았다. 쉬우니 생략

 

2. U집합의 두 개의 합 Set으로 저장하기

이 문제에서 특이한 부분은 같은 원소를 여러번 더해도 된다는 것이다.

예를들면.. 1 2 3 이 있는 집합이 있다. 2개의 합은

 

1 + 1

1 + 2

1 + 3

2 + 2

2 + 3

3 + 3

 

이렇게 6가지가 된다. 그래서 이중 for문을 쓰되, 자기 자신을 더하도록 조건을 주어야 한다. 그리고 1 + 3, 3 + 1 처럼 두 번 반복되지 않도록 해야한다.

for(i=0;i<N;i++){
    for(j=i;j<N;j++)
        twoSumSet.add(arr[i] + arr[j]);
}

 

3. Set과 U집합을 이용해 세 수의 합 최댓값 구하기

set은 이미 U의 원소 2개의 합이니까, set (2개의 합) + U의 원소 1개 = 3개의 합 이 될것이다. 이 식을 다르게 표시하면 set(2개의 합) = 3개의합 - U의 원소 1개  를 뜻한다. 3개의합 - U의 원소 1개 가 set에 있는지 찾으면 된다. set이므로 시간복잡도는 O(1)이다.

* 3개의 합은 U안에 있으므로 이렇게 풀 수 있는것이다. 예시 {2 3 5 10 18} 에서 18 - 10 = 8, 8은 5+3이고 이미 Set에 두 개의 합으로 계산되어 있음.

// 세 번째 수를 선택하고, 선택된 수에서 두 수의 합을 뺀 결과가 HashSet에 있는지 확인, 18 - 10 = 8
for(i=N-1;i>=0;i--){
    for (j = i - 1; j >= 0; j--) {
        pick = arr[i] - arr[j];
        if(twoSumSet.contains(pick) && arr[i] > max)
            max = arr[i];
    }
}

---

아래는 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class BOJ2295 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, i, j, pick, max = -999, k = 0;
        N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        Set<Integer> twoSumSet = new HashSet<>();

        for(i=0;i<N;i++)
            arr[i] = Integer.parseInt(br.readLine());

        // arr 정렬
        Arrays.sort(arr);

        // 두 개의 합 저장
        for(i=0;i<N;i++){
            for(j=i;j<N;j++)
                twoSumSet.add(arr[i] + arr[j]);
        }

        // 세 번째 수를 선택하고, 선택된 수에서 두 수의 합을 뺀 결과가 HashSet에 있는지 확인, 18 - 10 = 8
        for(i=N-1;i>=0;i--){
            for (j = i - 1; j >= 0; j--) {
                pick = arr[i] - arr[j];
                if(twoSumSet.contains(pick) && arr[i] > max)
                    max = arr[i];
            }
        }

        // 출력
        System.out.println(max+"");
    }
}

 

Set 인터페이스 주요 메서드

• boolean add(E e): 지정된 요소를 추가합니다.
• boolean contains(Object o): 지정된 요소가 포함되어 있는지 확인합니다.
• boolean remove(Object o): 지정된 요소를 제거합니다.
• int size(): 집합의 요소 개수를 반환합니다.
• void clear(): 모든 요소를 제거합니다.
• boolean isEmpty(): 집합이 비어 있는지 확인합니다.
• Iterator<E> iterator(): 요소를 반복하는 반복자를 반환합니다.