배열과 리스트: '좋은 수' 구하기 (백준 1253)

 

1253번: 좋다

 

 

 

 

난이도: 골드 4

풀이: 투 포인터 알고리즘을 적용한다. 시작 지점에서 포인터를 배열의 시작점과 끝점에 위치하여 차례로 포인터 간의 위치를 줄여가는 알고리즘을 이용한다. 참고로 배열 A의 숫자 크기는 플러스 마이너스 무려 10억까지 지정할 수 있게 해야 하므로, 데이터형은 int보다는 long를 이용해야 한다.

 

 

 

import java.io.*;
import java.util.*;
 
public class P1253 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N            = Integer.parseInt(st.nextToken());
        long A[]    = new long[N];
        st                = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < N; i ++) {
            A[i]        = Long.parseLong(st.nextToken());
        }
        
        Arrays.sort(A);
        
        int count    = 0;
        
        for (int k=0; k < N; k++) {
            long find     = A[k];
            int i            = 0;
            int j            = N-1;
            
            while (i < j) {
                if (A[i] + A[j] == find) {
                    if (i != k && j != k) {
                        count ++;
                        break;
                    } else if (i == k) {
                        i ++;
                    } else if (j == k) {
                        j --;
                    }
            } else if (A[i] + A[j] < find) {
                i ++;
            } else {
                j --;
            }
            }
 
        }
        System.out.println(count);
        
    }
}