백준 - 3273 두 수의 합 [투포인터]

 

3273번: 두 수의 합

 

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. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/3273.%E2%80%85%EB%91%90%E2%80%85%EC%88%98%EC%9D%98%E2%80%85%ED%95%A9