[백준] 1253번. 좋다(JAVA)

문제

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

---

풀이(30분)

import java.io.*;
import java.util.*;

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()); // 숫자의 개수
        int[] numbers = new int[N]; // 입력 받은 값

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

        for(int i =0 ; i < N ; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(numbers); // 투포인터를 위한 정렬

        int answer = 0;
        for(int i = 0 ; i < N ; i++){
            int left = 0;
            int right = N-1; // 인덱스를 위한 길이 - 1
            while(true){
                if(left == i){ // 찾고자 하는 값이 left와 동일하다면 불가능
                    left++;
                    continue;
                }
                if(right == i) { // 찾고자 하는 값이 right와 동일하다면 불가능
                    right--;
                    continue;
                }

                // 결과를 찾을 수 없다.
                if(left >= right) break; // 투포인터 초과
                
                if(numbers[left] + numbers[right] > numbers[i]) { // 두 합이 찾고자 하는 값보다 크다면
                    right--;
                    continue;
                }
                if(numbers[left] + numbers[right] < numbers[i]) { // 두 합이 찾고자 하는 값보다 작다면
                    left++;
                    continue;
                }
                answer++;
                break;
            }
        }
        System.out.println(answer);
    }
}

---

문제 풀이 전략

 

초기 2000개의 입력임에도 불구하고, 플마 10억까지라는 값을 보고 set와 map을 이용하려 문제를 해결하려고 했다.

 

하지만 n = 2000이기 때문에 각 n에 대해 시간복잡도가 O(N)인 투포인터를 사용해도 문제가 발생하지 않을 것이라는 걸 깨닫고 방향을 바꾸었다.

 

풀이법은 간단하게 투포인터를 활용하여, N만큼의 입력에 대해 모두 체크하여 정답을 확인해 주는 것이다.