PS/백준

[백준] 1253 좋다

HUN 2021. 4. 11. 09:35


 이분탐색을 통해 해결할 수 있다. 유의해야할 점은 이분탐색은 배열이 정렬되어있는 상태여야 하는 것, 그리고 배열의 수가 자연수라고 정의되어 있지 않기 때문에 0이 포함되는 경우를 생각해야된다.

 

0이 포함되는 경우 자기 자신을 더하는 경우가 발생할 수 있기 때문에 타겟이 되는 수를 제외한 배열에서 이분 탐색을 수행해야한다.

 

Python

 

from sys import stdin
readline = stdin.readline
N = int(readline())
arr = list(map(int, readline().split()))
def solve():
cnt = 0
arr.sort()
for i in range(len(arr)):
if binary_search(i, arr[i]):
cnt += 1
print(cnt)
def binary_search(i, target):
temp = arr[:i] + arr[i+1:]
left = 0
right = N - 2
while left < right:
cur = temp[left] + temp[right]
if cur > target:
right -= 1
elif cur < target:
left += 1
else:
return True
return False
solve()
view raw BOJ1253.py hosted with ❤ by GitHub

Java

 

import java.io.*;
import java.util.*;
public class BOJ1253 {
static int N;
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
solve();
}
public static void solve(){
int res = 0;
for(int i=0;i<N;i++){
int[] arrSplit = splitArray(i);
if(binarySearch(arr[i], arrSplit)){
res++;
}
}
System.out.println(res);
}
public static boolean binarySearch(int target, int[] arrSplit){
int left = 0; int right = N-2;
while(left < right){
int cur = arrSplit[left] + arrSplit[right];
if(cur > target){
right--;
} else if(cur < target){
left++;
} else {
return true;
}
}
return false;
}
public static int[] splitArray(int idx){
int[] temp = new int[N-1];
int i = 0;
for(int j=0;j<N;j++){
if(j==idx) continue;
temp[i] = arr[j];
i++;
}
return temp;
}
}
view raw BOJ1253.java hosted with ❤ by GitHub
728x90