[프로그래머스] 두 개의 수로 특정값 만들기

1. 문제

---

출처: [코딩테스트 합격자되기 - 자바편] 236페이지

 

 

2. 풀이 과정

---

이 문제를 딱보자마자 들었던 생각은 이중 for문 이었다.

이중 for문을 통해 두 개의 수를 뽑아서 합을 구한 다음, 그 합이 target과 일치하는지를 확인하면 된다.

그렇게 되면 시간복잡도가 O(N^2)이 된다.

 

하지만 애석하게도 이 문제의 입력최대 크기는 10000이다. O(N^2)으로는 풀 수가 없다.

 

따라서 생각의 방향을 바꿨다. 

arr[i]와 그 외 다른 배열의 원소 arr[k]를 더했을 때 target이 되게 하는 arr[k]가 배열에 있는지를 체크한다.

 

이때 arr[k]가 배열에 있는지 체크하는 과정이 핵심인데 그냥 배열로 조회한다면 O(N)이 소요되겠지만 해시를 이용한다면 O(1)로 해결이 가능하다.

 

3. 내 코드

---

public static boolean solution(int[] arr, int target) {

    Set<Integer> set =  new HashSet<>();

    for (int i : arr) {
        if(set.contains(target - i)) {
            return true;
        }

        set.add(i);
    }

    return false;
}

시간 복잡도

• O(N)

HashSet은 HashMap의 value가 없는 버전이라고 생각하면 된다.

key만 있으면 되므로 HashMap이 아닌 HashSet을 사용했다.

 

4. 피드백

---

• 특정 값이 있는지 조회할 때 HashSet을 사용한다면 O(1)로 조회할 수 있다.