[투포인터] 백준 1253

1. 문제
2. 문제 분석
3. 슈도코드
4. 구현

문제

주어진 N (1 <= N <= 2000) 개의 수 중, 두 수의 합으로 표현되는 수 찾기
- 숫자 범위 : ( 숫자 <= 1,000,000,000 )
- 2초 이내 풀어낼 것 ( CPU 계산 : 1초에 1억번 연산 )
- N세제곱은 시간 오버이므로, 주의하며 구현

 

문제분석

• N제곱 안에 문제를 풀어내야함 (시간제한)
• 투포인터 ( O(n) )를 사용하여 , 두수의 합으로 표현되는 수 찾기 가능
  • 단, 두수의 합으로 표현되는 수의 개수를 찾는것이기에  한가지 조합만 있으면 됨

[투포인터]
* 투포인터 사용 전, 오름차순 정렬이 전제 조건임
1. Arr[i] + Arr[j] < M  //  i 증가
2. Arr[i] + Arr[j] > M  //  j 감소
3. Arr[i] + Arr[j] == M //  count 증가, i 증가, j 감소 

 

슈도코드

N (배열의 개수) 

for (N만큼 반복)
{
    A배열에 데이터 저장
}

A배열 정렬하기

for(N만큼 반복)
{
    변수 초기화 // (찾고자 하는 값: A[k] , 포인터 : i,j)
     while(i < j){
     {
          if( A[i] + A[j] == A[k] )
                두 포인터 i,j 가, k가 아닐때 결과값에 반영(조합 찾기 성공) 및 while 문 종료
                두 포인터 i,j 가, k가 맞을때 포인터 변경 및 계속 수행
          else if (k > M) 포인터 i 증가
          else 포인터 j 증가
       }
}

좋은 수의 개수 출력

 

구현

• 투포인터에서 j 초기화 값을 "size-1"로 둔 것은 전 범위를 기준으로 탐색하려는 목적 ( 음수도 가능하기에 arr[k] 보다 큰수도 고려해야함)
• k인덱스를 포함하면 안되므로, 제거해줘야하는 조건이 필요
  • 두개의 합을 이루는 "숫자"를 찾는것이므로, 해당 숫자가 두개의 합 조합에 들어가면 안됨

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

public class App {
    public static void main(String[] args) throws Exception {
        
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        
        int size =Integer.parseInt(buf.readLine());
        int []arr = new int[size];
        
        StringTokenizer st = new StringTokenizer(buf.readLine());

        for(int i=0; i<size; i++){
            if (st.hasMoreTokens()){
                arr[i] = Integer.parseInt(st.nextToken());
            }else{
                System.out.println("StringTokenizer 오류");
                break;
            }
        }
        
        Arrays.sort(arr);
        
        int result = 0;
        for(int k=0; k<size; k++){
            long find = arr[k];
            int i = 0;
            int j = size-1;
            
            while (i<j){
                if ( arr[i] + arr[j] == find ){
                    if (i != k && j != k){
                        result++;
                        break;
                    }else if(i == k){
                        i++;
                    }else if(j==k){
                        j--;
                    }
                }else if (arr[i] + arr[j] > find) {
                    j--;
                }else{
                    i++;
                }
            }
            
        }

        System.out.println("Result : " + result);

    }
}