[Algorithm] 백준 투포인터 문제 - 두 수의 합(3273) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 투포인터 문제 - 두 수의 합 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

1. 풀이 소스

 

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());

        TwoSum ts = new TwoSum(n);
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            ts.setMap(i, parseInt(st.nextToken()));
        }
        ts.setSum(parseInt(br.readLine()));
        ts.run();
        System.out.println(ts.getPair());;
    }
}

class TwoSum {

    int n; // n개의 입력
    int[] map; // 입력 배열
    int target; // 목표 합
    int pair; // 순서쌍 개수

    public TwoSum(int n) {
        this.n = n;
        map = new int[n];
    }

    void setMap(int i, int value) {
        map[i] = value;
    }

    void run() {
        Arrays.sort(map); // 오름차순 정렬하여 투포인터가 가능하도록 설정
        if (map.length == 1) return; // n이 하나인 경우 불가

        int left = 0; // 시작점
        int right = n - 1; // 끝 점

        while(left < right) { // 두 좌표가 교차된다면 종료 (left -> right, right -> left는 두 참조 이름만 바뀐 것이기 때문)

            int value = map[left] + map[right];

            if (target > value) left++; // 만약 목표보다 값이 작다면 left를 증가시켜서 합이 커지도록
            else if (target < value) right--; // 목표보다 크다면 right를 줄여서 합이 작아지도록
            else {
                pair++;
                left++; // left를 증가시켜서 무한루프를 막고 시작점을 현재 인덱스 다음으로 넘겨줌
            }
        }
    }

    void setSum(int target) {
        this.target = target;
    }

    int getPair() {
        return pair;
    }
}

 

2. 풀이 중점 사항 

 

일반적으로 두 수의 합 순서쌍을 구하는 경우는 이중 포문으로 구성하면 빅오 n^2이 나옵니다.

투포인터를 활용한다면 빅오 n으로 문제를 해결할 수 있습니다. 

 

오름차순 된 배열의 각 양 끝점을 포인터로 설정하고, 

목표로 하는 값 K보다 값이 작다면, left 포인터를 증가시킵니다.

 

배열은 오름차순 되어있기 때문에 1, 2, 3, 4, 5처럼 인덱스가 커질수록 단조 증가처리 됩니다.

따라서, 목표로 하는 값보다 작으므로 left를 증가시켜서 값을 늘리고,

늘렸더니 값이 다시 커진다면, right를 감소시켜서 값을 줄이는 방법입니다.

 

이러한 과정을 통해 원하는 k에 수렵하는 포인터 쌍을 구할 수 있습니다.