[Java] 두 수의 합 - 투 포인터 (Lv. Sliver3)

두 수의 합 - 투 포인터 (Lv. Sliver3)

---

1. 문제

2. 풀이

---

1. 문제

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

 

2. 풀이

import java.util.*;
import java.io.*;

public class Main {
    public static int two_pointer(int N, int[] a, int x) {
        int result = 0;
        int left = 0;
        int right = N-1;
        int sum = 0;

        Arrays.sort(a);
        
        while (left < right) {
            sum = a[left] + a[right];
            
            if (sum == x) {
                result++;
                left++;
                right--;
            } else if (sum < x) {
                left++;
            } else {
                right--;
            }
        }

        return result;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int x = Integer.parseInt(br.readLine());

        System.out.println(two_pointer(N, a, x));
    }
}

 

Arrays.sort(a); 를 통해 a 배열의 요소를 정렬 해줍니다. 

 

1

2

3

4

5

6

7

8

left

right

 

위와 같이 left는 a 배열의 가장 처음부터 시작하고 right는 a 배열의 가장 끝에서 시작합니다. 왼쪽 left 는 증가를 통해서 오른쪽으로 이동하고, 오른쪽 right는 감소를 통해서 왼쪽으로 이동하며 합을 구하게 됩니다. 이렇게 구하게 되면 (2, 4) (4, 2) 처럼 중복 쌍을 제외한 쌍을 구할 수 있습니다.

 

1

2

3

4

5

6

7

8

left

right

 

 현재 인덱스에 해당하는 값의 합이 x 보다 작을 때는 작은 쪽 인덱스를 올려서 값을 올려주고, x 보다 클 때는 큰 쪽 인덱스를 내려서 값을 낮춰줍니다.

 

1

2

3

4

5

6

7

8

left

left, right

 

while문을 돌면서 인덱스들이 한 지점에서 서로 만나게 되었을 때 종료되고 결과가 도출됩니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3