[백준 1253] 좋다 (투 포인터)

문제는 다음과 같다.

 

풀이

숫자 3은 1과2로 이루어지고 4는 3과1 ... 10은 1과9 로 합쳐지듯이 다른 수 두개의 합으로 나타낼 수 있다면 그 수를 좋은 수 라고하는 것이다. 이 문제를 풀기 위해선 정렬과 투 포인터를 이용하여 해결하면 된다.

 

for(k를 0부터 N까지 반복)

{

변수 초기화하기(찾고자 하는 값 find, 포인터 i, 포인터 j)

while(i < j)

{

 if(A[i] + A[j] == 찾고자 하는 값)

   두포인터 i,j가 k가 아닐때 결괏값에 반영 및 while 문 종료

   두 포인터 i,j가 k가 맞을때 포인터 변경 및 계속 수행하기

else if(A[i] + A[j] < 찾고자 하는 값) 포인터 i 증가

else 포인터 j 감소

}

}

좋은수의 개수 출력하기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        int result = 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) {
                        result++;
                        break;
                    }
                    else if (i == k) {
                        i++;
                    }
                    else if (j == k) {
                        j--;
                    }
                }
                else if (A[i] + A[j] < find) {
                    i++;
                }
                else {
                    j--;
                }
            }
        }
        System.out.print(result);
    }
}

느낀점

처음에 두번이나 실패했는데 그 이유가 i가 k와 같을때와 j가 k와 같을때를 생각을 못했다.