Check If N and Its Double Exist — 어떤 값과 그 두 배가 함께 있는지 확인하기

값과 그 두 배가 함께 있는지 확인하기, 어떤 문제인가요?

LeetCode 1346번 문제는 이렇게 주어집니다.

정수 배열 arr가 주어집니다. 서로 다른 두 인덱스 i, j가 존재해서 arr[i] == 2 * arr[j]를 만족하는지 확인하세요.

정답은 Boolean입니다.

• 조건을 만족하는 두 원소가 있으면 true
• 끝까지 없으면 false

예시는 이렇습니다.

• arr = [10,2,5,3] → true
  • 10 == 2 * 5
• arr = [3,1,7,11] → false
  • 어떤 값도 다른 값의 두 배가 아님

제약은 다음과 같습니다.

• 2 <= arr.length <= 500
• -1000 <= arr[i] <= 1000

이 문제의 핵심은 단순히 "두 배 값이 있는가"가 아니라, 서로 다른 위치의 두 원소를 사용해야 한다는 점입니다. 특히 0은 0 == 2 * 0이므로, 0 하나만으로는 부족하고 0이 두 개 있어야 조건을 만족합니다. 이 글에서는 모든 쌍을 확인하는 풀이부터, 이전에 본 값을 HashSet에 저장해서 한 번에 찾는 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

조건을 양쪽 방향으로 보기

조건은 다음 하나입니다.

arr[i] == 2 * arr[j]

현재 보고 있는 값을 num이라고 하면, 이전에 본 값들 중에서 확인해야 할 가능성은 두 가지입니다.

이전 값 == num * 2
num == 이전 값 * 2

두 번째 조건은 이렇게 바꿔 쓸 수 있습니다.

이전 값 == num / 2

다만 정수 배열이므로 num / 2는 num이 짝수일 때만 정확합니다. 예를 들어 7은 어떤 정수의 두 배가 될 수 없으므로 7 / 2를 확인하면 안 됩니다.

Phase 1. 모든 쌍을 확인하기

가장 직접적인 방법은 서로 다른 모든 인덱스 쌍을 확인하는 것입니다.

fun checkIfExist(arr: IntArray): Boolean {
    for (i in arr.indices) {
        for (j in arr.indices) {
            if (i != j && arr[i] == 2 * arr[j]) {
                return true
            }
        }
    }

    return false
}

arr = [10,2,5,3]이라면:

• i = 0, arr[i] = 10
• j = 2, arr[j] = 5
• 10 == 2 * 5이므로 true

이 방식은 이해하기 쉽고, i != j 조건도 그대로 코드에 드러납니다. 하지만 원소 개수가 n개일 때 모든 쌍을 확인하므로 시간 복잡도는 O(n^2)입니다.

제약이 최대 500이라 통과는 가능하지만, 같은 문제를 더 깔끔하게 풀 수 있습니다.

Phase 2. 이전에 본 값을 HashSet에 저장하기

배열을 왼쪽에서 오른쪽으로 한 번만 보면서, 이미 지나온 값들을 HashSet에 저장합니다.

현재 값 num에 대해 이전 값들 중 다음 중 하나가 있으면 바로 정답입니다.

• num * 2
• num / 2, 단 num이 짝수일 때만

fun checkIfExist(arr: IntArray): Boolean {
    val seen = HashSet<Int>()

    for (num in arr) {
        if (seen.contains(num * 2)) {
            return true
        }

        if (num % 2 == 0 && seen.contains(num / 2)) {
            return true
        }

        seen.add(num)
    }

    return false
}

arr = [10,2,5,3]를 따라가 봅시다.

num = 10
seen = {}
20 없음, 5 없음 -> 10 저장

num = 2
seen = {10}
4 없음, 1 없음 -> 2 저장

num = 5
seen = {10, 2}
10 있음 -> true

5를 볼 때 이전에 10을 봤기 때문에 10 == 2 * 5 관계를 찾을 수 있습니다.

시간 복잡도는 O(n)이고, 추가 공간은 O(n)입니다.

왜 먼저 검사하고 나중에 저장하나요?

현재 값을 seen에 먼저 넣으면 같은 인덱스를 자기 자신과 매칭할 위험이 생깁니다.

특히 0에서 문제가 됩니다.

arr = [0, 1]

만약 0을 먼저 저장하고 바로 0 * 2를 찾으면, 0 하나만으로도 true가 되어 버립니다. 하지만 문제는 i != j를 요구하므로 이 경우는 false가 맞습니다.

그래서 순서는 항상 다음과 같아야 합니다.

1. 이전에 본 값들에서 조건을 만족하는 값이 있는지 확인
2. 현재 값을 seen에 추가

이렇게 하면 seen에는 항상 현재 인덱스보다 앞에 있는 값만 들어 있으므로 i != j 조건이 자연스럽게 지켜집니다.

0은 어떻게 처리되나요?

0은 조금 특이합니다.

0 == 2 * 0

하지만 인덱스가 달라야 하므로, 0이 두 개 있어야 합니다.

최종 풀이에서는 이 조건도 별도 예외 처리 없이 해결됩니다.

arr = [0, 0]

첫 번째 0:
seen = {}
0 없음 -> 저장

두 번째 0:
seen = {0}
0 있음 -> true

반대로 arr = [0, 1]이면 첫 번째 0을 검사할 때 seen이 비어 있으므로 true가 되지 않습니다.

음수도 같은 방식으로 처리됩니다

배열에는 음수도 들어올 수 있습니다.

arr = [-2, -4]

이 경우:

-4 == 2 * -2

이므로 정답은 true입니다.

최종 풀이에서 num = -4를 볼 때:

num / 2 = -2
seen에 -2가 있음

이 되어 자연스럽게 true를 반환합니다. 양수와 음수를 나눠서 생각할 필요는 없습니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[10,2,5,3]	true	10 == 2 * 5
[3,1,7,11]	false	조건을 만족하는 쌍이 없음
[0,0]	true	서로 다른 두 0 사용 가능
[0,1]	false	0이 하나뿐임
[-2,-4]	true	-4 == 2 * -2
[7,14]	true	14 == 2 * 7

두 풀이를 다시 비교

풀이	시간	공간	특징
모든 쌍 확인	O(n^2)	O(1)	조건을 그대로 코드로 옮긴 풀이
HashSet 한 번 순회	O(n)	O(n)	이전 값만 저장하면서 빠르게 확인

마무리

1. 조건은 arr[i] == 2 * arr[j]이고, 두 인덱스는 서로 달라야 합니다 — 같은 원소를 두 번 쓰면 안 됩니다
2. 현재 값 num 기준으로 num * 2와 num / 2를 모두 확인해야 합니다 — 관계가 어느 방향으로 나올지 모르기 때문입니다
3. num / 2는 num이 짝수일 때만 확인합니다 — 홀수는 정수의 두 배가 될 수 없습니다
4. 현재 값을 저장하기 전에 먼저 검사해야 합니다 — 그래야 i != j 조건을 지킬 수 있습니다
5. HashSet 풀이의 시간 복잡도는 O(n)입니다 — 배열을 한 번만 순회하면서 조건을 찾습니다