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

백준알고리즘 3273번 : 두 수의 합 (Solved.ac 난이도 Silver3)

 

더해서 자연수 x를 만족하는 쌍이 몇개 있는지 확인하는 문제이다.

 

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

3273번: 두 수의 합

 

 

처음에는 100만까지 숫자가 주어진다는 것을 확인하여

Int 배열의 크기를 100만으로 만들고,

받아온 숫자값에 1을 넣어서 숫자가 1이면 count한다, 라는 식으로 풀어보았다.

예제를 반영하자면

arr[5]=arr[12]=arr[7]=arr[10]=arr[9]=arr[1]=arr[2]=arr[3]=arr[11]=1 같은 식이다.

x가 13이므로 절반인 6까지비교하면서

arr[5]=1이고 arr[13-5]=1이믄 count, 와 같은 방식으로 했는데,

100%가까이에서 실패하였다. 확인해보니 java에서 1차원 배열의 경우 (당연하지만) 최대 크기가 있고,

int 타입의 1차원 배열의 100만은 택도 없고 10만~25만 정도가 최대인것 같다.

 

그래서 투포인터 탐색을 이용하여 풀었다.

 

풀이 과정

---

1. 배열에 값을 담아 정렬한뒤 포인터 a는 배열 맨 앞을, 포인터 b는 맨 끝을 지정한다.
2-1. arr[a]+arr[b]의 값이 x와 같다? count++, 포인터 a++, 포인터 b--
2-2. arr[a]+arr[b]의 값이 x보다 크다? 포인터 b-- (합이 더 작아야져야하므로 더 작은 숫자를 찾는다.)
2-3. arr[a]+arr[b]의 값이 x와 같다? 포인터 a++ (합이 더 커져야하므로 더 큰 숫자를 찾는다.)
3. count 개수를 출력한다.

 

 

 

 

소스 ▽

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main { // [Silver3] 3273번 : 두 수의 합
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        int[] arr = new int[testCase];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < testCase; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        int sum = Integer.parseInt(br.readLine());

        int x = 0;
        int y = arr.length-1;
        int cnt = 0 ;
        while (x<=y && x<=arr.length-1 && y>=0){
            if (arr[x]+arr[y]==sum && x!=y) {
                cnt++;
                x++;
                y--;
            }else if (arr[x]+arr[y]<sum){
                x++;
            }else {
                y--;
            }

        }
        System.out.println(cnt);
    }
}