[백준] 2018_수들의 합5 - JAVA

백준_2018

1253번: 좋다

 

투 포인터

투 포인터의 기초적인 설명은 아래 링크 참고.

[백준] 2018_수들의 합5 - JAVA

 

이번 문제도 저번 문제(주몽)와 마찬가지로 정렬을 이용하면 더욱 간단하게 풀 수 있다. 그래서 정렬 후 투 포인터를 저번 문제처럼 배열의 양 끝에 각각 배치하면 되는데 여기서 중요한 점은 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안된다. 그리고 배열의 양 끝이라 표현했지만 좋은 수의 판별이 되는 수의 전 index가 배열의 끝이 된다.

투 포인터의 이동 원칙

arr[i] + arr[j] > k 이면 j--;
arr[i] + arr[j] < k 이면 i++;
arr[i] + arr[j] == k 이면 i++; or j--; or count;

 

이번에도 문제 예제에 적혀있는 배열로 풀이 과정을 보자.

이번엔 세 개의 색깔이 등장한다. 1은 i, 2는 j, 3은 k이다. k는 좋은 수의 판별이 되는 대상이다. 투 포인터의 이동 원칙에 따라 1 + 2 == 3이니 자기 자신인지 판별한 후에 아니면 count++;를 한 후 break;로 빠져나오면 되고, i == k인 경우엔 i++; j == k인 경우엔 j--;를 해주면 된다. 이런식으로 배열의 마지막까지 반복한다.

주의할 점은 입력 된 배열에 음수 값이 있다는 점이다. 문제를 자세히 못보고 첫 번째 배열, 두 번째 배열은 더할게 없으니 반복문을 n-2번만큼 돌려도 될 거 같아 for문의 i를 2부터 시작하니 틀렸다. 그러니 음수 값도 염두해두고 배열을 처음부터 끝까지 다 돌려야한다.

 

코드

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

public class Main {
    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());

        st = new StringTokenizer(br.readLine());

        long[] arr = new long[n];
        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) {
                    if(i != k && j != k) {
                        count++;
                        break;
                    } else if(i == k) {
                        i++;
                    } else if(j == k) {
                        j--;
                    }
                } else if (arr[i] + arr[j] < find) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        System.out.println(count);
    }
}

 

제출 결과