[Gold IV] 좋다 - 1253
성능 요약
메모리: 12688 KB, 시간: 124 ms
분류
이분 탐색, 자료 구조, 정렬, 두 포인터
제출 일자
2024년 6월 18일 00:30:07
문제 설명
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
출력
좋은 수의 개수를 첫 번째 줄에 출력한다.
접근 방법
1. 각 값에 대하여 투 포인터를 사용하기 위해서 정렬한다.(n log n)
2. 그 후 차례대로 값을 확인하면서 그 값이 좋다수인지 확인해준다.( n )
3. 투포인터를 이용해서 확인하되 해당 값이 확인해주는 인덱스인지 아닌지 확인해줘야 함( n )
-> n 은 최대 2,000임으로 n * n인 4,000,000으로 안전하게 풀이 가능하다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* 30분 컷
*/
public class BOJ_1253 {
static int[] arr;
static int N;
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];
// Input
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}// Input End
Arrays.sort(arr);
int answer = 0;
for (int i = 0; i < N; i++) {
// 좋다수면 증가
if (check(i)) {
answer++;
}
}
System.out.println(answer);
}
private static boolean check(int idx) {
int l = 0, r = N - 1;
int checkNum = arr[idx];
while (l < r) {
int sum = arr[l] + arr[r];
// 좋다수인지 확인하는 값이라면 증가 시켜준다.
if (l == idx || sum < checkNum) {
l++;
} else if (r == idx || sum > checkNum) {
r--;
}
// 위 조건 분기 둘 다 해당 안될 시 좋다 수
else {
return true;
}
}
// 좋다수가 아닌 경우
return false;
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 2374번 : 같은 수로 만들기 Gold4(골드4) - JAVA[자바] (0) | 2024.06.18 |
---|---|
[백준] 10282번 : 해킹 Gold4(골드4) - JAVA[자바] (1) | 2024.06.18 |
[백준] 1092번 : 배 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |
[백준] 2229번 : 조 짜기 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |
[백준] 20208번 : 진우의 민트초코우유 Gold5(골드5) - JAVA[자바] (0) | 2024.06.15 |