[코드트리 챌린지] 두 수의 합

 

 

문제 : 두 수의 합

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

코드트리 기준 IM 난이도의 문제이다.

 

원소의 개수 n과 두 수의 합이 될 k가 공백을 사이에 두고 주어지고, 

두 번째 줄에는 n개의 정수가 공백을 사이에 두고 주어집니다. 수가 중복되어 주어질 수 있으며 

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

 

사실 이 문제를 실력 진단에서 두 번 만났는데, 아쉽게도 이번에도 풀지 못하고 따로 풀어보려고 했지만 결국 해설을 찾아보고 풀었다.

아이디어 자체는 간단했다. 문제 조건을 보면 a + b = k이고, 이 식을 변경하면 k - a = b로 바꿔줄 수 있다.

그래서 풀이는 아래와 같다.

1. HashMap에 k - a 즉 b가 존재하는지 찾고, 존재하는 수 만큼 결과값에 더해준다.

2. 이후 존재 여부과 관계 없이 현재 확인중인 배열의 숫자를 HashMap에 넣어주고, 만약 이미 존재한다면 value값에 1을 더해준다.

 

시간복잡도를 계산하면

1. 모든 원소들에 대한 for문 - O(N)이고

나머지는 상수 시간에 계산이 가능하다.

 

코드는 아래와 같다

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
    static int n;
    static long k;
    static long[] inputArr;
    static void input() throws IOException{

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Long.parseLong(st.nextToken());

        inputArr = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            inputArr[i] = Long.parseLong(st.nextToken());
        }
    }

    static void pro() throws IOException{

        int cnt = 0;
        HashMap<Long, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long diff = k - inputArr[i];
            if (hashMap.containsKey(diff)) cnt += hashMap.get(diff);
            hashMap.put(inputArr[i],hashMap.getOrDefault(inputArr[i], 0) + 1);
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws IOException{
        input();
        pro();
    }

}