문제 설명
서로 다른 양의 정수 n개로 이루어진 수열이 주어진다.
이때 두 수 ai, aj를 더해서 x가 되는 쌍의 개수를 구하는 문제이다.
조건은 다음과 같다.
1 ≤ i < j ≤ n
ai + aj = x즉, 같은 원소를 두 번 쓰면 안 되고
서로 다른 두 위치의 원소를 골라 합이 x가 되는 경우의 수를 구해야 한다.
입력
첫째 줄
n둘째 줄
수열의 원소들셋째 줄
x조건
1 ≤ n ≤ 100000
1 ≤ ai ≤ 1000000
1 ≤ x ≤ 2000000출력
합이 x가 되는 두 수의 쌍의 개수를 출력한다.
입력 예시
9
5 12 7 10 9 1 2 3 11
13출력 예시
3문제 해결 아이디어
처음에는 모든 두 수를 직접 비교하는 방식으로 생각할 수 있다.
예를 들어
- 첫 번째 수와 나머지 수 비교
- 두 번째 수와 그 뒤의 수 비교
- 이런 식으로 모든 쌍을 확인
이 방법은 구현은 쉽지만,
입력 크기가 최대 100000이기 때문에 시간이 오래 걸릴 수 있다.
내가 작성한 풀이
나는 이중 반복문을 사용해서
모든 (i, j) 쌍을 직접 검사했다.
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String[] arr = br.readLine().split(" ");
int result = 0;
int num = Integer.parseInt(br.readLine());
for(int i = 0; i < n-1; i++) {
for(int j = i+1; j < n; j++) {
if(Integer.parseInt(arr[i]) + Integer.parseInt(arr[j]) == num) {
result++;
}
}
}
bw.write(result + "\n");
bw.flush();
}
}왜 시간초과가 발생했을까
이 코드의 핵심 문제는
모든 쌍을 직접 비교하는 이중 반복문이다.
반복 구조를 보면
첫 번째 원소와 나머지 비교
두 번째 원소와 나머지 비교
...즉 시간 복잡도는
O(N²)가 된다.
문제에서 n의 최대값은
100000이므로
100000 × 100000 = 100억수준의 비교가 발생할 수 있다.
이는 1초 제한 안에 처리하기 어렵다.
또한 내 코드에서는 반복문 안에서 매번
Integer.parseInt(arr[i])
Integer.parseInt(arr[j])를 호출하고 있어서
불필요한 문자열 → 정수 변환도 계속 발생한다.
즉 시간초과의 원인은
- 이중 반복문 사용
- 반복문 내부에서
parseInt()반복 호출
이라고 볼 수 있다.
강의 풀이
강의에서는 숫자의 범위를 이용해서
등장 여부를 배열에 기록하는 방식으로 해결했다.
코드
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] a = new int[N];
for (int i = 0; i < N; i++)
a[i] = sc.nextInt();
int X = sc.nextInt();
int[] cnt = new int[1000001];
for (int i = 0; i < N; i++)
cnt[a[i]]++;
long ans = 0;
for (int i = 1; i <= (X - 1) / 2; i++)
if (X - i <= 1000000)
ans += (long)cnt[i] * cnt[X - i];
System.out.println(ans);
}
}강의 풀이 아이디어
문제 조건에서 각 수의 범위는
1 이상 1000000 이하이다.
즉 특정 숫자가 존재하는지 여부를
배열 인덱스로 바로 확인할 수 있다.
예를 들어
cnt[5] = 1이면 숫자 5가 존재한다는 뜻이다.
그 다음 i를 1부터 (X - 1) / 2까지 확인하면서
i + (X - i) = X를 만족하는 쌍이 존재하는지 검사하면 된다.
이 방식의 장점은
모든 두 수를 직접 비교하지 않아도 된다는 점이다.
두 풀이 방식 비교
| 방식 | 특징 |
|---|---|
| 내 풀이 | 모든 쌍을 직접 비교 |
| 강의 풀이 | 숫자 존재 여부를 배열로 기록 후 보수값 확인 |
내 풀이는 직관적이지만 느리고,
강의 풀이는 숫자 범위를 이용해 훨씬 빠르게 처리할 수 있다.
시간 복잡도
내 코드
이중 반복문 사용
O(N²)N = 100000이면 시간초과 가능성이 매우 높다.
강의 코드
- 입력 저장:
O(N) - 등장 여부 기록:
O(N) - 보수값 탐색:
O(X)
실제로는 제한된 범위 내에서 매우 빠르게 동작한다.
핵심 개념
이 문제의 핵심은 다음과 같다.
1. 브루트포스는 위험하다
두 수의 합 문제에서
모든 쌍을 직접 확인하면 O(N²)가 된다.
입력 크기가 크면 시간초과 가능성이 높다.
2. 값의 범위를 활용할 수 있다
이 문제는 수의 범위가 명확하다.
1 ≤ ai ≤ 1000000그래서 해시나 배열을 이용해
숫자의 존재 여부를 빠르게 확인할 수 있다.
3. 보수값(complement) 개념
어떤 수 i가 있을 때
합이 X가 되려면 필요한 다른 수는
X - i이다.
즉 두 수의 합 문제는
항상 보수값을 떠올리는 것이 중요하다.
정리
처음에는 이중 반복문으로 모든 경우를 직접 확인했지만
입력 크기가 커서 시간초과가 발생했다.
이 문제는 단순히 두 수를 비교하는 문제가 아니라
수의 범위와 보수값 개념을 활용해 더 빠르게 해결해야 하는 문제였다.
이번 문제를 통해 배운 점은 다음과 같다.
N이 큰 경우O(N²)는 위험할 수 있다.- 값의 범위가 작거나 제한되어 있으면 배열을 활용할 수 있다.
- 두 수의 합 문제에서는
X - 현재값형태의 보수값을 떠올리는 것이 중요하다.
