[BAEKJOON] 두수의 합 : 3273번

1. 문제 파악

---

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제

2. 접근 방법

---

해당 문제는 수열 내 서로 다른 양의 정수를 더하여 x 값이 되는 쌍의 갯수를 구하는 문제입니다.

필자의 경우, 해당 문제를 보고 두 수의 합? 투 포인터를 활용한 풀이를 수행하면, 되겠구나 생각이 들었습니다.

투 포인터는 정렬된 배열 내에서 양 끝 가장자리의 index부터 시작하여 연산을 진행하며 점차 중간 index로 이동하는 연산을 말합니다.

처음 구현 시, 양끝에서 점차 가운데로 이동한다는 것을 구현하고자 서로 다른 두 수의 합을 연산 했을 때, 해당 값이 같지 않은 경우(x 보다 크거나 작은 경우) 연산을 다르게 해줘야 한다는 점을 간과했습니다.

이로 인해, 연산 결과의 분기를 같거나 같지않는 경우 2가지로만 생각하여 구현한 결과 오류가 발생했습니다.

        while(flagS < flagE) {
            long sum = nums[flagS] + nums[flagE];
            if (x == sum){
                count++;
            }
            flagS++;
            flagE--;
        }

if절로 분기를 구분할 때, 연산결과가 x와 같은지만 비교할 것이 아니라, x보다 크다면 큰 index를 -1 해주고, x보다 작다면 작은 index를 +1 해주는 식으로 연산하여, 결과를 보장할 수 있도록 값을 보정해줬어야 합니다. 이 방식으로 수정해주면, 다음과 같이 구현됩니다.

        while(flagS < flagE) {
            int sum = nums[flagS] + nums[flagE];
            if (x == sum) {
                count++;
                flagS++;
                flagE--;
            } else if (x > sum) {
                flagS++;
            } else {
                flagE--;
            }
        }

위와 같이 구현한 결과 정상적으로 로직이 수행되었습니다.

3. 제출 코드

// 메모리 : 24904KB, 시간 : 296ms
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main{
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(br.readLine());
        
        int[] nums = new int[n];
        for(int i=0; i<n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);
        
        int flagS = 0;
        int flagE = n-1;
        int count = 0;
        while(flagS < flagE) {
            int sum = nums[flagS] + nums[flagE];
            if (x == sum) {
                count++;
                flagS++;
                flagE--;
            } else if (x > sum) {
                flagS++;
            } else {
                flagE--;
            }
        }
        
        System.out.println(count);
        br.close();
    }
}