https://www.acmicpc.net/problem/2295
이진탐색이 아닌 SET 자료형으로도 풀 수 있다. 합을 set에 저장해두고 contains로 확인하는 방법이다. 로직은 똑같다.
contains는 O(1)이다.
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.valueOf(br.readLine());
int[] num = new int[n];
for(int i=0;i<n;i++){
num[i]=Integer.valueOf(br.readLine());
}
Arrays.sort(num);
int[] num2= new int[n*(n+1)/2];
//num2는 원소 2개의 합으로 나올 수 있는 수의 집합 N^2
int index =0;
for(int i=0;i<n;i++){
for(int j=i; j<n;j++){
num2[index++] = num[i]+num[j];
}
}
Arrays.sort(num2);
// num1의 최대값부터 낮은수로 내려가면서 N
// num에서 하나 고르고 num2에서 이진탐색으로 해당 값이 있는지 체크 N * 2logN
// 총 N*N*logN
for(int i=n-1;i>=0;i--){
for(int j=0; j<n;j++){
int goal = num[i];
if(Arrays.binarySearch(num2,goal-num[j])>=0){
System.out.println(goal);
return;
}
}
}
}
}
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
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();
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]);
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]);
}
System.out.println(ans);
}
}
'Problem Solving > 구간합' 카테고리의 다른 글
TreeSet 메소드(미완) (0) | 2024.02.14 |
---|---|
BOJ17232 생명게임* (1) | 2024.02.11 |
BOJ 19951 태상이의 훈련소 생활 (0) | 2024.02.09 |
BOJ11660 구간 합 구하기 5(R) * (0) | 2024.02.09 |
BOJ16713 Generic Queries (0) | 2024.02.08 |