Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

26. 투 포인터

투 포인터 알고리즘과 meet in the middle 알고리즘을 배워 봅시다.

Java / Python

1. 두 수의 합

3273번

양끝에서 포인터를 좁혀가면서 A[i] + A[j] = x인 모든 경우를 찾는 문제 (더 쉬운 방법이 있지만, 연습을 위해 투 포인터를 써봅시다.)

이번 문제는 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하는 문제입니다.

1.배열을 입력받아 정렬(오름차순)을 해줍니다.

• 정렬 후 3가지 경우에 따라 투 포인터 탐색을 진행하면 된다.

2. start, end 를 이용하여 arr[start]와 arr[end]를 더해줍니다. (tmp 변수에 저장)

• 두 수의 합이 x보다 큰 경우 - 더 큰 값을 더해야하므로 start+1
• 두 수의 합이 x보다 작은 경우 - 더 작은 값을 더해야하므로 end-1
• 두 수의 합이 x인 경우 - result+1 & start+1

3. 결과(result)를 출력합니다.

• Java

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

public class Main {        
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
        
		int N = Integer.parseInt(br.readLine());
        
		int[] arr = new int[N]; 
        
		StringTokenizer st = new StringTokenizer(br.readLine());        
		for(int i = 0; i < N; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
        
		int x = Integer.parseInt(br.readLine()); 
        
		Arrays.sort(arr);
        
		int start = 0;
		int end = N - 1;
		int sum = 0;
		int result = 0;
       
		while(start < end) {
			sum = arr[start] + arr[end];
			if(sum == x) result++;
            
			if(sum <= x) start++;
			else end--;
		}
        
		bw.write(result + "\n");
        
		bw.flush();
		br.close();
		bw.close();
	}
}

• Python

import sys

N = int(sys.stdin.readline())
arr = sorted(list(map(int, sys.stdin.readline().split())))
x = int(sys.stdin.readline())

arr.sort()
start, end = 0, N - 1
result = 0

while start < end:
    tmp = arr[start] + arr[end]
    if tmp == x: 
        result += 1
        start += 1
    elif tmp < x:
        start += 1
    else: end -= 1
print(result)