1. 문제 분석
[문제 링크](https://www.acmicpc.net/problem/1253)
2. 접근 방식
- 배열의 양 끝에 포인터를 둔다.
- 현재 Good이 되는 수인지 검산 한다. (포인터 2개의 합이 현재 검산 중인 수보다 크면 오른쪽 포인터를 한 칸 내린다.) (포인터 2개의 합이 현재 검산 중인 수보다 작으면 왼쪽 포인터를 한 칸 올린다.)
- 숫자는 음수도 가능하므로, 제약없이 전체에 대해서 계산 해야한다. 이는 O(n^2)의 시간 복잡도가 들지만, 계산해야할 총 데이터 수가 2000 이므로 10^3 이라 계산이 괜찮다.
3. 코드 분석
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int [] 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);
int cnt = 0;
for (int i = 0; i < N; i++) {
int temp = arr[i], start = 0, end = N-1;
while (start != end){
if(start == i) {
start++;
continue;
}
if(end == i) {
end--;
continue;
}
if(arr[start] + arr[end] > temp){
end--;
}else if(arr[start] + arr[end] < temp){
start++;
}else if(arr[start] + arr[end] == temp){
cnt++;
break;
}
}
}
System.out.println(cnt);
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[백준] 17298 오큰수 JAVA (0) | 2024.07.02 |
---|---|
[백준] 11399 ATM (0) | 2024.07.02 |
[백준] 2018 수들의 합 5 Java 풀이 (0) | 2024.06.28 |
[백준] 11659 구간 합 구하기 4 쉬운 풀이 여러가지 풀이 java (0) | 2024.06.22 |
[백준] 구간 합 구하기 5 쉬운 풀이, 여러가지 풀이 java (0) | 2024.06.22 |