[JAVA] 백준 3273 두 수의 합

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

3273번: 두 수의 합

 

- n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai+aj = 을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램 

 

문제 풀이 

 

투 포인터 (Two Pointers)

 

[Algorithm] 39강 : 투 포인터(Two Pointers) 알고리즘의 정의와 구현 — 나무늘보의 블로그 (tistory.com)

[Algorithm] 39강 : 투 포인터(Two Pointers) 알고리즘의 정의와 구현

[파이썬, Python] 백준 3273: 두 수의 합 (tistory.com)

[파이썬, Python] 백준 3273: 두 수의 합

- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

- 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현 

- 정렬되어 있는 두 리스트의 합집합, 병합정렬의 conquer 영역의 기초로 사용됨

 

- 시작 지점이 끝 지점보다 커지기 전까지 반복하며 각 인덱스를 가진 수를 더해서 target과 같은지 확인

 

- 두 수의 합이 target과 같다면 start ++, end --를 수행

- 두 수의 합이 target보다 작다면 수가 커져야 하므로 start ++

- 두 수의 합이 target보다 크다면 수가 작아져야 하므로 end--

 

- 최종적으로 카운트된 값을 출력 

 

정답 

 

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

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 target = Integer.parseInt(br.readLine());
        
        Arrays.sort(arr); //오름차순 정렬
        
        int start = 0;
        int end = arr.length-1;
        int ans = 0;
        
        while(start<end)
        {
            int sum = arr[start]+arr[end];
            
            if(sum == target)
            {
                ans++;
                start++;
                end--;
            }
            else if(sum > target)
            {
                end--;
            }
            else
            {
                start++;
            }

        }
        
        bw.write(String.valueOf(ans));
        
        bw.flush();
        bw.close();
        
    }
        
}