Q 3273 두 수의 합

💡 문제 요약 및 분석

a[n] 배열에서 a[i] + a[j] = x 가 되는 경우의 수를 모두 찾아라.

💡 알고리즘 설계

✅ n의 범위가 최대 100,000이기 때문에 이중for문을 쓰면 타임아웃이 된다. map 을 활용하자.

1. 입력

   • 표준입력으로 배열 int[N] a 생성

2. 연산

   • for문으로 배열 a 반복
   • a[i] - x 를 key 로 갖는 값이 있는지 확인하고 있으면 count++
   • a[i] 를 key로 추가한다.

3. 출력

   • count 변수를 출력한다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int n = 0, c = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int n = read();
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = read();
        }
        int x = read();

        int count = 0;
        Map<Integer, Integer> memo = new HashMap<>();
        for (int i = 0; i < n; i++) {
            count += memo.getOrDefault(x - A[i], 0);
            memo.put(A[i], 1);
        }
        System.out.println(count);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n)	O(n)

💡 다른 풀이

아예 공간을 더 써서 시간을 절약하는 풀이법도 있었다. n개만큼의 배열 arr을 만들어서 arr[read()] 로 입력되는 값에 true 표시하여 모든 위치를 방문하는 로직도 있었다. 이 경우 중복을 방지하기 위해 x / 2 + 1 부터 검사를 시작한 것이 인상적이었다. 내가 사용한 HashMap도 평균 조회 시간이 O(1) 로 상수 시간만큼 걸리지만, 배열의 경우 상수가 훨씬 작다고 한다.

class Main {
    static int read() throws Exception {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }
    
    public static void main(String[] args) throws Exception {
        int n = read();
        boolean[] arr = new boolean[1000001];
        for (int i = 0; i < n; i++) {
            arr[read()] = true;
        }
        int x = read();
        
        int answer = 0;
        for (int i = x / 2 + 1; i < 1000001; i++) {
            int remain = x - i;
            if (remain <= 0) break;
            if (arr[i] && arr[remain]) answer++;
        }
        System.out.println(answer);
    }
}