[알고리즘]백준 1253: 좋다

 

해결방법

수를 순서대로 순회하면서 투 포인터로 서로 다른 두 수의 합으로 나타낼 수 있는 수의 개수를 구한다. ⇒ O(N^2) (N≤2000)

*수의 위치가 다르면 값이 같아도 다른 수이다.

 

코드

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

// O(N^2)
public class Main_1253_G4_좋다_투포인터 {
    static int N;
    static int[] numbers;

    public static void main(String[] args) throws IOException{
        // 1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numbers); // 정렬

        // 2. answer 값 계산
        int answer = 0;
        for(int i=0; i<N; i++){
            int n = numbers[i];
            int left = 0;
            int right = N-1;

            while(left<right){
                int s = numbers[left]+numbers[right];

                if(s==n){
                    if(left==i){
                        left++;
                    }else if(right==i){
                        right--;
                    }else{
                        answer++;
                        break;
                    }
                }else if(s>n){
                    right--;
                }else if(s<n){
                    left++;
                }
            }
        }

        // 3. 출력
        System.out.println(answer);
    }
}

 

링크

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