[백준] 3273 두 수의 합 [Java]

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

3273번: 두 수의 합

 

요즘 강의를 들으면서 문제를 풀고 있는데 시간초과로 인해 틀리는 경우가 많아지고 있다...

이 문제도 풀면서 어 이중포문으로 풀면 쉬울거 같은데? 하면서 이것도 시간초과 되려나 생각했지만

역시나 시간초과였다..

아직 기본적인 문제만 풀 줄 알아서 검색해봤다.

이 문제는 투 포인터 라는 알고리즘을 사용한다.

투 포인터란?

투 포인터

 

투 포인터 알고리즘을 적용해서 이 문제를 풀어보면

1. 배열을 입력받아 오름차순으로 정렬을 한다.
2. 왼쪽 원소를 가리킬 left 와 오른쪽 원소를 가리킬 right 포인터를 설정한다.
   • 두 수의 합이 sum보다 큰 경우 더 큰 값을 더해야 하므로 left + 1
   • 두 수의 합이 sum보다 작은 경우 더 작은 값을 더해야 하므로 right - 1
   • 두 수의 합이 sum인 경우 answer + 1, left + 1, right + 1

그렇게 해서 내가 푼 코드 이다.

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

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 arr[] = new int[n];
        HashSet<Integer> set = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(br.readLine());

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

        int left = 0;
        int right = n - 1;
        int answer = 0;

        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == x) {
                answer++;
                left++;
                right--;
            } else if (sum > x) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(answer);
    }
}

투 포인터의 시간복잡도는 O(n)이고, 이중 포문의 경우에는 O(n^2) 이므로 훨씬 빠르다.

역시 아직은 자료구조에 대해 공부를 안해서 시간복잡도에 관한 부분이 많이 부족하다. ㅠㅠ