[백준] 3273번 두 수의 합 (자바 풀이)

문제

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

3273번: 두 수의 합

풀이

이 문제는 두 가지 풀이가 가능하다.

 

첫번째는 Set을 이용한 방법이다. a + b = X 라는 식을 만족한다면, a = X-b 도 만족한다. 따라서 모든 원소를 Set에 넣은 다음, 첫 원소부터 탐색하며 X-i번째 원소가 Set에 존재한다면 두 수의 합이 X가 되는 것이므로 count 해준다. 이때 주의할 점은 이렇게 모든 원소를 탐색하면 (a,b)와 (b,a)가 중복으로 count 되므로 정답을 2로 나누어줘야 한다.

나는 이 방법을 사용하여 풀었지만, 알고리즘 분류를 보니 정렬, 투 포인터로 분류되어 있어 투포인터 방식도 사용해보기로 했다.

 

두번째는 투포인터를 이용한 방법이다. int 배열 arr[]에 모든 원소를 저장한뒤, 오름차순으로 정렬한다. 이후 왼쪽 원소를 가리킬 left와 오른쪽 원소를 가리킬 right 포인터를 설정한다. 이 두 포인터는 아래와 같이 이동한다.

 

1. arr[left]+arr[right] == X 이면 left++, right--

2. arr[left]+arr[right] > X 이면 right--

3. arr[left]+arr[right] < X 이면 left++

 

예를 들어 아래와 같은 예시를 보자. 

9
5 12 7 10 9 1 2 3 11
13

배열을 정렬하면 다음과 같다.

1 2 3 5 7 9 10 11 12

왼쪽 포인터를 L, 오른쪽 포인터를 R이라고 하자.

1 2 3 5 7 9 10 11 12
L                       R

arr[L] + arr[R] == 13 -> ans = 1, L++, R--

1 2 3 5 7 9 10 11 12
  L                 R

arr[L] + arr[R] == 13 -> ans = 2, L++, R--

1 2 3 5 7 9 10 11 12
     L          R

arr[L] + arr[R] == 13 -> ans = 3, L++, R--

1 2 3 5 7 9 10 11 12
        L    R       

arr[L] + arr[R] > 13 -> ans = 3, R--

1 2 3 5 7 9 10 11 12
        L R          

arr[L] + arr[R] < 13 -> ans = 3, L++

1 2 3 5 7 9 10 11 12
           L
           R

종료, ans = 3

코드

1. HashSet을 이용한 방법

import java.util.*;
import java.io.*;
 
public class Baekjoon_3273 {
    static int N,X, ans;
    static int arr[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        HashSet<Integer> set = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            set.add(arr[i]);
        }
        X = Integer.parseInt(br.readLine());
 
        for(int i=0; i<N; i++) {
            if(set.contains(X-arr[i])) {
                ans++;
            }
        }
        System.out.println(ans/2);
    }
}
 

2. 투포인터를 이용한 방법

import java.util.*;
import java.io.*;
 
public class Baekjoon_3273 {
    static int N,X, ans;
    static int arr[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        HashSet<Integer> set = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        X = Integer.parseInt(br.readLine());
 
        Arrays.sort(arr);
        
        int left=0, right = N-1;
        while(left < right) {
            int sum = arr[left]+arr[right];
            if(sum == X) {    // 같다면 count
                ans++;
                left++;
                right--;
            }else if(sum > X) {    // 더 크다면
                right--;
            }else {    // 더 작다면
                left++;
            }
        }
        
        System.out.println(ans);
    }
}
 

결과

1. HashSet을 이용한 방법

 

2. 투 포인터를 이용한 방법

 

HashSet을 이용한 방법이 시간을 더 빨랐고, 투 포인터를 이용한 방법이 메모리는 조금 더 절약됐다.