[코드트리 조별과제] 두 수의 합 (HashMap)

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

문제

n개의 정수가 입력으로 주어지고, 이 중 서로 다른 위치에 있는 두 개의 수를 뽑아 더했을 때 k가 되는 가짓수를 구하는 프로그램을 작성해보세요.

입력 형식

출력형식

입력으로 주어진 수들 중 서로 다른 위치에 있는 두 개의 수를 골랐을 때 두 수의 합이 k가 되는 가짓수를 출력합니다.

풀이

배열에 입력된 값을 집어넣고 2개의 숫자 조합을 2중 반복문으로 골라 더한 값을 HashMap의 Key로 두고 가짓수를 Value 저장해서 값을 구하고자함 => 메모리 초과

메모리 초과 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        long K = Long.parseLong(st.nextToken()); 

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N]; 
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        HashMap<Long, Integer> map = new HashMap<>();

        for(int i=0; i<N; i++){
            for(int j=i+1; j<N; j++){
                map.put((long) arr[i] + (long) arr[j], map.getOrDefault((long) arr[i] + (long) arr[j], 0)+1); 
            }
        }

        System.out.println(map.get(K));
    }
}

 

실패 이유 

모든 가능한 두 수의 합을 계산하고 이를 해시맵에 저장하기 때문에 메모리 초과가 남.

배열의 크기 N이 최대 100,000일 경우, 가능한 쌍의 수는 N(N-1) / 2 로 약 50억 개에 달함. 이렇게 많은 수의 합을 해시맵에 저장하게 되면 메모리 사용량이 매우 커져 메모리 제한을 초과하게 됨. 또한 시간 복잡도가 O(N^2)이다. 

따라서 모든 가능한 합을 미리 계산하고 저장하지 않고, 필요한 순간에 계산하고 바로 결과를 활인하는 방식으로 접근해야한다. 즉, 배열을 순회하면서 구하고자 하는 값(K)에서 현재 배열의 값(arr[i])을 뺀 값이 HashMap에 존재하는지 체크하고 그 숫자가 나온 횟수(Value)값을 정답에 더해주면 된다.

JAVA 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        long K = Long.parseLong(st.nextToken()); 

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N]; 
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        HashMap<Long, Integer> map = new HashMap<>();
        long count = 0;

        for(int i=0; i<N; i++){
            if(map.containsKey(K-arr[i])){
                count += map.get(K - arr[i]); 
            }
            map.put((long) arr[i], map.getOrDefault((long) arr[i], 0)+1); 
        }

        System.out.println(count);
    }
}