[백준-3273번]두 수의 합

사용언어 : JAVA

1.문제

 - 문제설명

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

- 입력

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

- 출력

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

-예제 입력/출력

입력
9(입력되는 배열의수)
5 12 7 10 9 1 2 3 11(배열)
13(두수의 합)

출력
3

 

2.나의풀이

 

 

이 문제는 9개의 자연수 배열인 [5,12,7,10,9,1,2,3,11]중 두 수를 더했을때 13이 나오는 값의 카운트를 출력해야 하는 문제다.

 

처음에는 이중 for문을 이용하여 완전탐색하는 방법을 사용했지만 시간초과가 발생 했다.

그래서 찾아본 방법중에 투포인터 알고리즘이 있었다.

 

투포인터(Two Pointers)
- 리스트에 순차적으로 접근해야 할 때 두개의 점 위치를 기록하면서 처리하는 알고리즘

 

투포인터 알고리즘을 이용하여 문제를 풀어 보았다.

 

1. 배열을 오름차순으로 정렬 시킨다.

2. 하나의 포인터는 왼쪽(start), 하나의 포인터는 오른쪽(end)에서 출발한다.

3. 3가지 경우의 수에 따라 포인터의 값을 변경 한다.

 - target(원하는 합)의 값이 배열의 start, end 포인터가 가리키는 값의 합과 일치할 경우(target = arr[start] + arr[end])

   : start포인터 증가, end 포인터 감소, cnt 증가

 - target(원하는 합)의 값이 배열의 start, end 포인터가 가리키는 값의 합보다 작을 경우(target < arr[start] + arr[end])

   : end 포인터 감소

 - target(원하는 합)의 값이 배열의 start, end 포인터가 가리키는 값의 합보다 큰 경우(target > arr[start] + arr[end])

   : start포인터 증가

3. 코드 구현(JAVA)

 

import java.util.*;
import java.io.*;
 
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());
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).sorted().toArray();
        int target = Integer.parseInt(br.readLine()), cnt = 0;
        int start = 0, end = n-1;
        while(start < end){
            int sum = input[start] + input[end];
            if(sum == target){
                end--; start++;
                cnt++;
            }else if(sum>target)
                end--;
            else
                start++;
        }
        System.out.println(cnt);
    }
}