[코드트리 조별과제] HashMap 활용

코드트리에 HashMap을 활용하는 문제에서 임의의 두 수의 합을 구하는 문제가 있다.

 

수가 중복해서 나올 수 있는점을 고려해야 하기에 문제가 까다롭지만, HashMap을 사용하면 상수시간에 가까운 시간복잡도로 문제를 해결할 수 있다.

 

HashMap을 굳이 안쓰고 문제를 접근할 수도 있다 (투포인터, 합이 0에 가까운 또다른 수 찾기 (이분탐색))

 

하지만 숫자가 매우 큰경우에는 일반적인 배열의 인덱스로 활용하기 힘들기에 해싱 자료구조를 채택하는것이 좋다.

 

문제중에 두 수의 합과 세 수의 합이 있는데, 초안으로는 이분탐색과 투포인터로 해결할 실마리가 보였지만 반례에 막혔고

 

중복된 수에 대한 경우의수 예외를 적절하게 처리해주면 된다.

 

이를 위해 미리 수에 대한 카운팅 Map을 만들어주고

 

현재 소모할 숫자를 기준으로 경우를 세어주면 2개를 통해 k를 만드는 경우의 수를 구할 수 있다.

 

세 수의 합은 두수의 합에서 숫자하나만 고정시켜놓고, 그 밖의 범위에서 나머지 숫자를 찾으면 된다.

 

즉, 고정시킬 인덱스가  i 이고, 뽑을 두 수가 j, k일 때 자연수 i, j, k (i, j, k < arr.length )에서 찾아야할 수 find를 찾는 방법은

 

i < j < k 이면서 arr[i] + arr[j] + arr[k] = find 인 경우를 세어주면 된다.

 

import java.util.*;
import java.io.*;
public class Main {
    static int n;
    static int k;
    static int [] arr;
    static StringTokenizer stk;
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(stk.nextToken());
        k = Integer.parseInt(stk.nextToken());
        
        stk = new StringTokenizer(bf.readLine());
        arr = new int[n];
        for(int i= 0;i<n;i++){
            arr[i] = Integer.parseInt(stk.nextToken());
        }
        int cnt = 0;
        for(int i= 0;i<n-2;i++){
            // 수 하나 고정시켜놓고
            // 나머지 수들 중에서 2개를 뽑는 조합을 찾는다.
            // 이 때 고정수 기준으로 매번 새로운 조합인것을 연산에서 잊으면 안된다.
            HashMap<Integer, Integer> map = new HashMap<>();

            // 아래는 두수의 합이 k - arr[i] 만큼이 되는 경우를 뽑는것
            int find = k - arr[i];
            for(int j= i+1;j<n;j++){
                map.put(arr[j], map.get(arr[j]) == null ? 1 : map.get(arr[j]) + 1);
            }
            
            for(int j = i+1;j<n;j++){
                map.put(arr[j], map.get(arr[j])-1);
                if(map.containsKey(find - arr[j])){
                    cnt += map.get(find - arr[j]);
                }
            }
        }
        System.out.println(cnt);
    }
    
}