[JAVA] 백준 1253번 : 좋다

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

이 문제를 보자마자 전에 풀었던 것 처럼 '투 포인터'를 사용하면 된다는 생각이 떠올랐다. 하지만, 첫 접근 이후 가장 중요한 사실인 '정렬'을 놓쳐 접근에서 조금 시간이 걸렸다..

투 포인터는 '리스트에 순차적으로 접근'할 때 사용하는 알고리즘이다. 즉, 리스트 안에 값들이 정렬되어 있어야 한다. 아래 알고리즘에서 sum 값과 target값을 비교해서 sum이 더 적으면 가장 큰 수인 A[end]값을 늘려주어야 하기 때문이다. 그래서 정렬을 한 후 알고리즘을 적용해 주어야 한다.

또한, 시작 index값과 끝 index값을 처음에는 전역변수로 선언을 해 주어 goodNumCnt값이 제대로 나오지 않았었다. for문을 반복하여 각 배열의 방에 접근한 이후 start값과 end값을 update 해 주어야 하는데, 전역변수로 선언하면 첫 for문 시에만 start와 end값이 반영되고 이후부터는 계속 같은 값이 반복되기 때문이다.

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

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 goodNumCnt = 0; //좋은 수의 개수
        String[] input = br.readLine().split(" ");
        int[] A = new int[N]; //각각의 수. 위치가 다르면 다른 수
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(A); //투 포인터를 사용하기 위하여 정렬 해 주어야 함

        for (int i = 0; i < N; i++) { //정렬된 배열을 반복
            int target = A[i]; //비교할 수
            int start = 0; //시작 index값
            int end = N - 1; //끝 index 값
            while (start < end) { //배열의 index값을 맨 끝까지 반복
                int sum = A[start] + A[end];
                if (sum == target) { //합계가 비교할 수와 같으면
                    if (start != i && end != i) { //다른 위치의 수라면
                        goodNumCnt++; //count 값 증가
                        break; //이미 합계가 같은 수가 있으므로 더 구할 필요가 없으므로 break
                    } else if (start == i) { //시작 index가 비교해야 할 값의 index와 같다면
                        start++;
                    } else if (end == i) { //끝 index가 비교해야 할 값의 index와 같다면
                        end--;
                    }
                } else if (sum < target) { //합계가 적다면
                    start++; //시작 값(작은 값)을 늘려 합계를 더 크게 함
                } else if (sum > target) { //합계가 더 크다면
                    end--; //끝 값(큰 값)을 줄여 합계를 더 적게 함
                }
            }
        }
        System.out.println(goodNumCnt);
        br.close();
    }
}

점점 실력이 느는 것이 보여서 너무 기쁘다.. 앞으로 더 많은 문제들을 풀며 알고리즘 실력을 쌓아야겠다.