[Java/Map] 코드트리. 두 수의 합

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

🤔 Intuition

주어지는 숫자의 범위가 넓으므로 해시맵을 활용하여 좌표를 압축해야 할 것으로 봤다.

 

두 수의 합이 k가 되는가를 구하기 위해서는 각 숫자의 개수끼리 곱해주고, 동일한 숫자에 대하여는 조합 공식을 이용하여 개수를 구해줬다.

🔎 Algorithm & Complexity

* @algorithm hash-map
* @time O(N) : 키 개수만큼 순회
* @memory O(N) : 키-값 쌍 개수

👨🏻‍💻 Logic

1. 각 숫자별로 몇 개씩 존재하는지 hashmap에 저장

2. key pair끼리 곱하여 경우의 수 연산 + key가 동일한 경우(3 + 3 = 6과 같은 경우)에는 조합 공식을 이용하여 연산

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

/**
 * 결국 경우의 수 문제
 * 내가 알아야 하는 건, 해당 숫자가 몇 개씩 있는가?
 *
 * 맵에 <key : value = 숫자 : 개수> 넣어두고, keySet() 순회하면서 경우의 수 세주고, visited 관리해서 pass 할 거 패스해주자.
 * 이 때, 주어지는 숫자의 범위가 20억이므로 배열로 visited 관리가 불가능. 따라서 visited를 map으로 관리해주자.
 */
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());
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Boolean> visited = new HashMap<>();

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int key = Integer.parseInt(st.nextToken());
            map.put(key, map.getOrDefault(key, 0) + 1); // 개수 먼저 count
            visited.put(key, false);
        }

        int ans = 0;
        for (Integer key : map.keySet()) {
            if (!visited.getOrDefault(key, true) && !visited.getOrDefault(k - key, true)) {
                int a = map.getOrDefault(key, 0);
                int b = map.getOrDefault(k - key, 0);
                if (key != k - key) {
                    ans += a * b;
                } else {
                    ans += a * (a - 1) / 2;
                }
                visited.put(key, true);
                visited.put(k- key, true);
            }
        }
        System.out.println(ans);
    }
}