[코드트리 조별 과제] 세 수의 합

 

B형 대비를 위해 HashMap 공부를 하는 도중에 풀었던 문제다.

N개의 정수 중 서로 다른 위치의 정수 3개를 골라 K를 만들 수 있는 경우의 수를 구하는 문제인데,

생각보다 까다롭기도 하고, 쉬운 방법으로 풀어낼 수 있어 글을 작성하기로 했다.

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

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

        st = new StringTokenizer(br.readLine());

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

        int[] arr = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
		
        // 한 개를 미리 넣음
        map.put(arr[0], 1);

        int ans = 0;
        for(int i = 1; i < n; i++) {
        	// i가 바뀔 때마다 set 초기화
            set = new HashSet<>();
            for(int j = 0; j < i; j++) {
                int std = k - arr[i];
                int a = map.getOrDefault(arr[j], 0);
				
                // j가 이미 set에 있다면 넘어가기(중복 방지)
                if(set.contains(arr[j])) continue;

                int num = std - arr[j];
				
                // num이 이미 set에 있다면 넘어가기(중복 방지)
                if(set.contains(num)) continue;
				
                // 둘이 같다면 aC2를 해야 함
                if(num == arr[j]) {
                    ans += (a * (a-1)) / 2;
                // 다르다면 a * b로 도출
                } else {
                    int b = map.getOrDefault(num, 0);
                    ans += (a * b);
                }

                set.add(arr[j]);
            }
            // map에 arr[i] 추가
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        System.out.println(ans);
    }
}