개발일지/Algorithm
백준 - 3273 두 수의 합 [투포인터]
E-room
2023. 10. 21. 17:05
728x90
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
1. 문제 요약
자연수 수열이 주어지고 해당 수열의 수들 중, 두 수를 합하여 x와 같은 경우의 수를 구하라.
2. 접근 방법 - 투 포인터
- 배열을 오름차순으로 정렬합니다.
- 성능 향상 : x보다 작은 수들만 사용하도록 필터링
- i = 0, j = 수열의 크기 - 1
- arr[i] + arr[j] == x 일 경우
- answer += 1
- i += 1, j -= 1 (정렬을 했기 때문에, 해당 수들을 더했을 때, x가 나올 수 없음)
- arr[i] + arr[j] < x 일 경우
- i += 1 (합이 x보다 작기 때문에, i 위치의 수는 커져야 함)
- arr[i] + arr[j] > x 일 경우
- j -= 1 (합이 x보다 크기 때문에, j 위치의 수는 작아져야 함)
3. 파이썬
# arr 오름차순 정렬
answer = 0
i = 0
j = len(arr) - 1
while i < j:
add = arr[i] + arr[j]
if add == x:
answer += 1
i += 1
j -= 1
elif add < x:
i += 1
else:
j -= 1
print(answer)
4. 자바
// arr 오름차순 정렬
int answer = 0;
int i = 0;
int j = arr.length - 1;
while (i < j) {
int add = arr[i] + arr[j];
if (add == x) {
answer++;
i++;
j--;
} else if (add < x) {
i++;
} else {
j--;
}
}
System.out.println(answer);
5. 전체 코드
728x90