[Java] 백준 풀기 3273 - 두 수의 합

자바 백준 3273번

실버 3

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

3273번: 두 수의 합

 

 

 

 

 

문제 보기

분류: 정렬, 투 포인터

 

 

 

 

 

문제 풀기

입력된 숫자 수열을 오름차순 정렬을 하고 첫번째 index와 마지막 index를 시작으로 two-pointer technique을 사용하여 두 수의 합을 확인한다.

두 수의 합이 주어진 x와 같으면, 카운트를 늘리고 array의 다음 안쪽 두 수를 확인한다. 만약 두 수의 합이 x보다 작으면 오름차순 정렬된 array의 왼쪽 포인터의 index를 +1 하여 합을 증가시키고, 두 수의 합이 x보다 크면 왼쪽 포인터의 index를 -1 하여 합을 감소시켜 x를 만족하는지 찾는다. 이 과정은 왼쪽 끝과 오른쪽 끝에서 시작한 포인터가 서로 엇갈릴때까지 진행한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();  // 수열의 크기 입력
        int[] arr = new int[n];  // 수열을 저장할 배열
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();  // 수열의 각 원소 입력
        }
        
        Arrays.sort(arr);  // 배열을 오름차순 정렬
        
        int x = sc.nextInt();  // 합을 찾을 값 입력
        
        // 오름차순 정렬된 배열에서 ai + aj = x를 만족하는 쌍의 개수를 찾음
        int pairCount = findPairCount(arr, x);
        
        // 쌍의 개수를 출력
        System.out.println(pairCount);
    }
    
    // 주어진 오름차순 정렬된 배열에서 ai + aj = x를 만족하는 쌍의 개수를 반환하는 함수
    static int findPairCount(int[] arr, int x) {
        int pairCount = 0;
        int left = 0;
        int right = arr.length - 1;
        
        while (left < right) {
            int sum = arr[left] + arr[right];
            
            if (sum == x) {
                pairCount++;  // 조건을 만족하면 쌍의 개수 증가
                left++;  // 왼쪽 포인터를 오른쪽으로 이동하여 다음 값과 비교
                right--;  // 오른쪽 포인터를 왼쪽으로 이동하여 다음 값과 비교
            } else if (sum < x) {
                left++;  // 합이 작으면 왼쪽 포인터를 오른쪽으로 이동
            } else {
                right--;  // 합이 크면 오른쪽 포인터를 왼쪽으로 이동
            }
        }
        
        return pairCount;
    }
    
}