2022.02.24 61일차

백준 3273번 (두 수의 합)

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

나의 풀이

1. 시간복잡도 생각하기, x에 해당하는 경우는 a + (x - a) == x 일때만 해당
2. 오름차순으로 정렬 후 start, end 지정
3. 배열의 첫번째 수와 마지막 수 합 구하기
4. 합이 x랑 같은 경우 카운트 증가
5. 합이 x보다 작거나 같은 경우 start 증가
6. 합이 x보다 큰 경우 end 감소
7. start가 end보다 작을때까지 반복

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        int[] nArr = new int[n];
        st = new StringTokenizer(br.readLine());

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

        int count = 0;
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int start = 0;
        int end = n - 1;

        while (start < end) {
            int sum = nArr[start] + nArr[end];
            if (sum == x) {
                count++;
            }
            if (sum <= x) {
                start++;
            } else {
                end--;
            }
        }

        System.out.println(count);
    }
}

생각하기

• 두 포인터 문제
• ArrayList의 경우 remove(끝), add(끝), get / set일때만 사용하기 - 시간복잡도 O(1)