[백준] 1253: 좋다 JAVA

접근

처음에는 map을 사용해서, c = a + b에서 b의 존재 여부만 확인한다면 시간을 절약할 수 있을 것이라 생각했다. 근데 반례를 찾을수록 if문이 늘어나면서 일일이 확인해야 했기 때문에 가독성도 성능도 그닥 좋은 방법은 아닌 것 같아 투포인터 방식으로 수정했다. 아래는 내가 고려하지 못했던 경우들이다. 

• 음수도 들어온다는 점
  • 음수 + 음수 = 음수 의 경우도 가능함
• 서로 다른 두 수의 합으로만 구성되지 않을 수 있다는 점
  • 4 = 2 + 2
  • 2 = 2 + 0
  • 0 = 0 + 0

투포인터 방식의 풀이는 간단하다. 모든 입력값 N에 대해서 투포인터를 적용해 합으로 만들 수 있는 숫자가 있는지 확인하는 것이다. 단, i와 left, right는 각각 하나의 인덱스이므로 서로 다른 숫자여야 한다. 

 

코드

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 answer = 0;

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);

        // 투포인터 적용
        for (int i = 0; i < n; i++) {
            int num = arr[i];
            int left = 0, right = n-1;

            while(left < right){
                int cur = arr[left] + arr[right];
                
                if(cur == num){
                    if(left == i) left++;
                    else if(right == i) right--;
                    else {
                        answer++;
                        break;
                    }
                }
                else if(cur > num) right--;
                else left++;
            }
        }

        System.out.println(answer);
    }
}