[자바/해시맵] 코드트리 IM: 두 수의 합

Point of failure

처음에 시간복잡도를 고려하지 않고 2차원 loop를 이용하여 완전탐색으로 하려고 했다.

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 k = Integer.parseInt(st.nextToken());
        Map<Integer, Long> map = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        br.close();
        long tmp;
        int i, j;
        for (i = 1; i <= n; i++) {
            tmp = Integer.parseInt(st.nextToken());
            map.put(i, tmp); // 순서 + element 입력 (중복 허용)
        }
        int cnt = 0;
        for (i = 1; i <= n; i++) {
            for (j = i+1; j <= n; j++) {
                long res = map.get(i) + map.get(j);
                if (res == k) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }
}

하지만 N이 100,000 이하이므로 2중 루프만 되더라도 1000ms를 넘어버린다. 따라서 2중 루프를 로직에서 제외해야 한다.

 

Analysis

우선 주어진 숫자를 자주 조회해야 하며, 주어지는 숫자의 범위가 10의 -9제곱부터 9제곱까지이므로 매우 크다. 따라서 배열로 등장 횟수를 기록하려고 하게 되면 20십억 크기의 배열을 생성해야 하므로 메모리를 매우 크게 사용해야 한다. 그러므로 HashMap을 사용하여 각 인덱스만 관리하면 된다.

 

Algorithm

등장 횟수 세기 => 자료구조 - 해시맵

 

Logic

기본적으로 쌍을 이루는 숫자는 1번으로 세줘야 하므로 우선 HashMap에는 아무것도 넣어두지 않은 채로 생성한다. 그리고 주어지는 문자들을 Array에 담아두고, 차례대로 비교하면서, 쌍을 이루는 놈이 HashMap에 없는 경우는 처음 만난 경우이므로 우선 넘어가되, 어차피 쌍을 이루는 원소가 있다면 무조건 다시 호출될 것이므로 쌍을 이루는 원소에 대하여 HashMap에 +1을 해주면 된다. 그런 뒤에, 찾는 원소가 왔을 때 쌍을 이루는 원소가 얼마나 있었는지 HashMap에 저장되어 있으므로 이를 출력할 수 있게 한다.

public class 두_수의_합 {
    public static int n, k, ans;
    public static final int MAX_N = 100000;
    public static long[] arr = new long[MAX_N];
    public static Map<Long, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        ans = 0;
        for (int i = 0; i < n; i++) {
            long diff = k - arr[i];
            if (map.containsKey(diff)) {
                ans += map.get(diff);
            }
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
            } else {
                map.put(arr[i], map.get(arr[i]) + 1);
            }
        }
        System.out.println(ans);
    }
}