b.3273 두 수의 합

 

https://www.acmicpc.net/problem/3273

 

 

 

📌 자바(Java)로 푸는 두 수의 합 문제 - 백준 3273 

 

🔎 문제 개요

 

백준 3273번 - 두 수의 합 문제입니다.

정수 N개로 이루어진 수열이 주어질 때,

서로 다른 두 수를 더해서 target이 되는 경우의 수를 구하는 문제입니다.

조건은 다음과 같습니다:

• 한 쌍은 한 번만 셈

• 중복 없이, 오름차순 또는 내림차순 상관없이 쌍을 구성

 

---

💡 예제 입력

9  
5 12 7 10 9 1 2 3 11  
13

💡 예제 출력

3

➡ 5+8, 1+12, 2+11 총 3쌍이 존재

 

---

🛠 알고리즘 접근 방식

 

이 문제는 대표적인 투 포인터(Two Pointer) 기법으로 해결할 수 있습니다.

 

✏️ 주요 고려 사항

• 배열을 정렬한 후, 왼쪽 포인터(left)와 오른쪽 포인터(right) 를 양 끝에 배치

• 합이 target보다 크면 right를 왼쪽으로,

• 작으면 left를 오른쪽으로 이동

• 정확히 같으면 정답(answer)에 +1 후 양쪽 포인터 이동

 

---

🔹 Java 코드 해설

import java.io.*;
import java.util.*;

public class Main {

    static int N, target, answer;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        target = Integer.parseInt(br.readLine());
        answer = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr); // 투포인터를 위해 정렬

        int left = 0, right = N - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                answer++;
                left++;
                right--;
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }

        System.out.println(answer);
    }
}

 

 

---

🔍 코드 설명

 

📌 1. 입력 처리 및 배열 정렬

N = Integer.parseInt(br.readLine());
arr = new int[N];
// ...
Arrays.sort(arr);

✔ 입력된 수열을 정수 배열로 저장하고 정렬

✔ 정렬은 투 포인터 알고리즘을 적용하기 위한 전처리 작업

 

---

📌 2. 투 포인터 알고리즘 적용

int left = 0, right = N - 1;

while (left < right) {
    int sum = arr[left] + arr[right];

    if (sum == target) {
        answer++;
        left++;
        right--;
    } else if (sum > target) {
        right--;
    } else {
        left++;
    }
}

✔ left + right == target인 경우, 정답으로 처리하고 양쪽 포인터를 이동

✔ 합이 너무 크면 right 감소, 작으면 left 증가

✔ 중복 없이 모든 경우를 빠르게 탐색 가능

 

---

🏆 정리

 

✅ 핵심 포인트

 

✔ 정렬된 배열을 활용한 투 포인터 알고리즘

✔ 중복 없이 두 수의 합이 target이 되는 경우의 수 계산

✔ O(NlogN) 정렬 + O(N) 탐색으로 효율적인 해결

 

---

🎯 이 알고리즘의 장점

 

✅ 시간 제한이 엄격한 상황에서도 빠르게 동작

✅ 배열 내에서 조건에 맞는 쌍을 효율적으로 찾을 수 있음

✅ 기초적인 투 포인터 알고리즘 학습에 적합한 대표 문제

 

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊