백준 - 두수의 합 (실버 3)

이 문제는 투포인터 알고리즘을 사용하는 문제이다

 

 

투포인터

: 배열이나 리스트에서 '두 개의 포인터'를 사용하여

'특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘.

 

• 연속적인 값들을 이용해 푸는 문제에 적합
• 선형시간이 걸린다. 
• 배열이나 리스트가 정렬되어 있어야 한다.

 

<투 포인터 알고리즘 활용>

 

1. 투 포인터 합

: 주어진 배열에서 두 개의 숫자를 선택하여 합이 

특정한 값을 갖는지 확인하는 문제.

 

 

구현방법

1. left와 right라는 두 포인터를 배열의 양 끝에서 시작
2. left 값보다 right 값이 클 때까지 반복
3. left와 right의 합을 sum에 저장
4. 만약 sum이 target값과 같다면
   -> count 값을 증가, left는 오른쪽으로, right는 왼쪽으로 한 칸씩 이동
   만약 sum < target이라면
   -> left를 오른쪽으로 한칸 이동
   만약 sum > target이라면
   -> right를 왼쪽으로 한 칸 이동
5. 종료되면 count 값을 반환

 

 

코드

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

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());
        String[] str=br.readLine().split(" ");
        int x=Integer.parseInt(br.readLine());
        int[] num=new int[n];

        for(int i=0;i<n;i++){
            num[i]=Integer.parseInt(str[i]);
        }
        Arrays.sort(num);
        
        int cnt=0;
        int left=0;
        int right=n-1;
        
        while(left<right){
            int sum=num[left]+num[right];
            
            if(sum==x){
                cnt++;
                left++;
                right--;
            }
            else if(sum>x){
                right--;
            }
            else{
                left++;
            }
                
        }
        
        bw.write(Integer.toString(cnt));
        bw.flush();
        bw.close();
    }
}

 

 

x보다 큰 값은 배열에 담지 않았다.

그러다 보니 실행시간이 조금은 줄어들었다.

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

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());
        String[] str=br.readLine().split(" ");
        int x=Integer.parseInt(br.readLine());
        int[] num=new int[n];
        int a=0;

        for(int i=0;i<n;i++){
            a=Integer.parseInt(str[i]);
            if(x>a)
                num[i]=a;
        }
        Arrays.sort(num);
        
        int cnt=0;
        int left=0;
        int right=n-1;
        
        while(left<right){
            if(num[left]==0){ // 담지 않은 공간은 넘기기
                left++;
                continue;
            }
            
            int sum=num[left]+num[right];
            
            if(sum==x){
                cnt++;
                left++;
                right--;
            }
            else if(sum>x){
                right--;
            }
            else{
                left++;
            }
                
        }
        
        bw.write(Integer.toString(cnt));
        bw.flush();
        bw.close();
    }
}