[Java] 백준 1253 좋다

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

예제 입력

10
1 2 3 4 5 6 7 8 9 10

예제 출력

8

설명

n 개수만큼 숫자가 주어지면 주어진 숫자 중 두개의 숫자를 합쳐서 어떤 수를 나타낼 수 있으면 된다.

나는 정열 후 투 포인터 알고리즘 으로 문제를 풀었다.

배열 양 끝에 포인터 두개를 두고 각각의 포인터를 이동시키며 계산하는 방식이다.

예시를 보자.
k = 현재 숫자
k = 1 이라고 했을 때 i는 배열의 맨 처음부터 시작하고 j는 배열의 맨 끝에서 시작한다.

숫자가 담긴 배열을 a라고 했을 때
k 보다 작을 경우 a[i] + a[j] < k : i++
k 보다 클 경우 a[i] + a[j] > k : j--
k 과 같을 경우 a[i] + a[j] == : count++ break

이렇게 계산 할 수 있다.

만약 k 가 3이라면 i 가 1일 경우 j 가 2일 경우 k 를 나타낼 수 있다.

만약 k 가 9라면 i가 1일 경우 j가 8일 경우 k 를 나타낼 수 있다.

사실 오름차순으로 정렬이 되어있기 때문에 i가 움직일 일은 없을 것 같다.

코드

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        long [] arr = new long[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);
        
        int count = 0;
        for (int k = 0; k < n; k++) {
            long find = arr[k];
            int i = 0;
            int j = n -1;
            while (i < j) {
                if (arr[i] + arr[j] < find) {
                    i++;
                } else if (arr[i] + arr[j] == find) {
                	// k 와 다른 수 여야 한다.
                    if (i != k && j != k) {
                        count++;break;
                    } else if (i == k) {
                        i++;
                    }
                    else if (j == k) {
                        j--;
                    }
                }
                else j--;
            }
        }
        System.out.println(count);
    }
}