🔍문제
https://www.acmicpc.net/problem/1253
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
🤔발상
두 수의 합을 구하는 문제는 정렬된 배열일 경우, 양 끝에 포인터 지정하고, 포인터를 움직이면서 원하는 값보다 큰지 작은지를 판단하면서 포인터를 이동하는 투 포인터 알고리즘으로 해결할 수 있습니다.
🔦입출력
N의 수는 2천개이며, N의 값은 10억이므로 두 수의 합은 INT 범위 이내고 투포인터로 탐색할 때 오래걸리지 않는 수입니다. O(N)
📃의사코드
1. 숫자들을 오름차순으로 정렬한다.
2. 각 수마다 투포인터로 해당 수를 만들 수 있는지 확인
3. 만들 수 있다면 카운트를 증가시킨다.👨💻코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
Arrays.sort(arr);
String[] sarr = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(sarr[i]);
}
int count = 0;
for (int i = 0; i < n; i++) {
int start = 0;
int end = n - 1;
while (start < end) {
if (start == i) {
start++;
continue;
}
if (end == i) {
end--;
continue;
}
int sum = arr[start] + arr[end];
if (sum == arr[i]) {
count++;
break;
} else if (sum < arr[i]) {
start++;
} else {
end--;
}
}
}
System.out.println(count);
}
}
}🚀TIL
- - 투포인터 알고리즘을 알고있다면 쉽게 해결할 수 있는 문제입니다.
- 삼중 포인터 문제도 예전에 리트코드에서 풀어본 기억이 있는데, 재귀형식으로 포인터 하나를 고정한 뒤에, 다시 자신을 호출하여 2가지 변수를 선택하는 알고리즘이었습니다. 복습을 해두면 좋을 것 같습니다.
