[백준: Java] 2295 - 세 수의 합

[문제]

https://www.acmicpc.net/problem/2295

처음에는 세 용액 문제처럼 기준을 잡고 나머지 두 수에 대해 투 포인터로 탐색을 진행하려고 했습니다.

 

하지만 최대에 대한 기준이 없기 때문에 적용하지 못했고, 집합 자료구조를 이용해 만들어낼 수 있는 수를 체크하는 방식으로 문제를 풀이했습니다.

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int n;
	static int[] u;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(br.readLine());
		u = new int[n];
		for (int i = 0; i < n; i++)
			u[i] = Integer.parseInt(br.readLine());

		solve();
	}

---

[풀이]

	static void solve() {
		HashSet<Integer> check = new HashSet<>();
		for(int x: u)
			for(int y: u)
				check.add(x + y);

		for (int k = n - 1; k > -1; k--) {
			for (int z = k - 1; z > -1; z--) {
				if (check.contains(u[k] - u[z]))  // x + y = k - z
					answer = Math.max(answer, u[k]);
			}
		}
		
		System.out.println(answer);
	}

일단 두 수로 만들 수 있는 모든 값을 집합에 저장합니다.

집합의 자료주는 HashSet으로 O(1)의 시간복잡도로 저장된 값을 체크할 수 있습니다.

 

x + y + z = k가 성립하므로 x + y = k - z의 형태로 값을 저장합니다.

 

주의할 점은, 입력되는 값들이 중복이 아닐 뿐, 선택할 수 있는 수는 중복이 허용된다는 점입니다.

 

반복문을 통해 기준 값이 k를 선택하고, k가 아닌 값을 순차적으로 탐색합니다.

 

그렇게 k - z의 값이 집합에 있다는 것은 k를 만들 수 있는 있는 조건의 성립을 의미합니다.

 

그렇게 모든 탐색을 수행하며 최대의 k를 찾습니다.

 

해당 탐색의 경우 O(N^2)의 시간복잡도를 가지지만, N이 최대 10만이고 시간제한은 1초이므로 제한 안에 풀이가 가능합니다.

---

[전체 코드]

package 백준.골드;

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

public class BOJ_2295_세수의합 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int n;
	static int[] u;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(br.readLine());
		u = new int[n];
		for (int i = 0; i < n; i++)
			u[i] = Integer.parseInt(br.readLine());

		solve();
	}

	static void solve() {
		HashSet<Integer> check = new HashSet<>();
		for(int x: u)
			for(int y: u)
				check.add(x + y);

		for (int k = n - 1; k > -1; k--) {
			for (int z = k - 1; z > -1; z--) {
				if (check.contains(u[k] - u[z]))  // x + y = k - z
					answer = Math.max(answer, u[k]);
			}
		}
		
		System.out.println(answer);
	}
}

---