[백준] 1253번 - 좋다 (Java)(○)

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

1253번: 좋다

 

<입력범위>

N : 수의 개수 : 1 ~ 2,000

Ai : 정수 : 1 ~ 1,000,000,000

 

<풀이>

1. N개의 수 중 2개를 골라서 그 수의 합이 다른 어떤 수와 같다면 그 수를 GOOD이라고 한다.

2. 투 포인터를 이용해서 A[i] 값을 순차적으로 M으로 대입해서 투포인터 알고리즘으로 A[s] + A[e] == M 인 경우의 수를 찾는다.

 

<구현>

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

public class Main {
    static int N;
    static long M;
    static long A[];
    
	void Solve() {
        int count = 0;
        Arrays.sort(A);

        for (int i=0; i<N; i++) {
            M = A[i];
            // sIdx는 처음부터, eIdx는 마지막부터 시작
            int sIdx = 0, eIdx = N-1;
            while (sIdx < eIdx) {
                long sum = A[sIdx] + A[eIdx];
                if (sum == M) { // M을 찾으면 두 인덱스 모두 변경
                    if (sIdx != i && eIdx != i) { //본인을 포함한 수이면 안된다
                        count++;
                        break;
                    } else if (sIdx == i) {
                        sIdx++; // 같은 수가 있을 수 있으므로
                    } else {
                        eIdx--; // 같은 수가 있을 수 있으므로
                    }
                } else if (sum < M) { // M보다 작으면 더 큰 값이 필요함
                    sIdx++;
                } else { // M 보다 크면 더 작은 값이 필요함
                    eIdx--;
                }
            }
        }
        System.out.println(count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        N = Integer.parseInt(br.readLine());
        A = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            //A[i] = Integer.parseInt(st.nextToken());
            A[i] = Long.parseLong(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }

}