반응형
https://www.acmicpc.net/problem/1253
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 4088 | 961 | 655 | 22.416% |
문제
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
출력
좋은 수의 개수를 첫 번째 줄에 출력한다.
예제 입력 1 복사
10
1 2 3 4 5 6 7 8 9 10
예제 출력 1 복사
8
코드
/*
좋다
투포인터
*/
import java.io.*;
import java.util.*;
public class p1253 {
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());
}
process();
}
static void process() {
int ans = 0;
Arrays.sort(arr);
for (int i = 0; i < n; i++) {
if (possible(i)) ans++;
}
System.out.println(ans);
}
static boolean possible(int idx) {
int lo = 0;
int hi = n - 1;
int target = arr[idx];
while (true) {
if (lo == idx) lo++;
else if (hi == idx) hi--;
if (lo >= hi) break;
int sum = arr[lo] + arr[hi];
if (sum < target) lo++;
else if (sum > target) hi--;
else if (sum == target) {
return true;
}
}
return false;
}
}
반응형
'알고리즘 > [ Baekjoon ]' 카테고리의 다른 글
[ BOJ ][JAVA][1920] 수 찾기 (0) | 2021.08.20 |
---|---|
[ BOJ ][JAVA][2559] 수열 (0) | 2021.07.30 |
[ BOJ ][JAVA][13144] List of Unique Numbers (0) | 2021.07.30 |
[ BOJ ][JAVA][11066] 파일 합치기 (0) | 2021.07.27 |
[ BOJ ][JAVA][3055] 탈출 (0) | 2021.07.27 |