BOJ 3273 - 두 수의 합

문제

N개의 서로 다른 양의 정수 수열에서, 두 수의 합이 x가 되는 쌍의 수를 구하라.

입력

첫째 줄에 N, 둘째 줄에 수열, 셋째 줄에 x가 주어진다.

출력

합이 x인 쌍의 수를 출력한다.

예제

입력	출력
`9` `5 12 7 10 9 1 2 3 11` `13`	`3`

풀이

정렬 후 투 포인터로 합이 x인 쌍을 센다.

배열을 정렬한다
l=0, r=N-1에서 시작하여 arr[l] + arr[r]을 x와 비교한다
합이 x이면 cnt++하고 l++로 다음 쌍을 탐색한다
합이 x 이하이면 l++, 초과이면 r--한다

핵심 아이디어: 정렬된 배열에서 양 끝 투 포인터는 합이 특정 값인 쌍을 O(N)에 찾는다. 모든 수가 서로 다르므로 중복 처리가 불필요하다.

코드

package day399;
 
import java.io.*;
import java.util.*;
 
public class Day387BOJ3273두수의합 {
  static int N;
  static int[] arr;
 
  public static void main(String args[]) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
 
    N = Integer.valueOf(st.nextToken());
    st = new StringTokenizer(br.readLine());
    arr = new int[N];
    for (int i = 0; i < N; i++)
      arr[i] = Integer.valueOf(st.nextToken());
 
    Arrays.parallelSort(arr);
 
    int x = Integer.valueOf(br.readLine());
    int l = 0, r = N - 1, cnt = 0, sum = 0;
 
    while (l < r) {
      sum = arr[l] + arr[r];
      if (sum == x)
        cnt++;
 
      if (sum <= x)
        l++;
      else
        r--;
    }
    System.out.println(cnt);
    br.close();
  }
}

복잡도

시간: O(N log N)
공간: O(N)

문제