leetcode 287, Find the Duplicate Number

문제 설명

n+1 만큼의 정수를 포함하고 있는 정수형 배열 nums가 있다. 이때 각 정수의 범위는 [1, n] 까지이다. 해당 배열에서 오로지 하나의 정수만 반복이 된다고 할 때, 반복이 되는 정수를 찾아서 반환하라.

 

이때 배열을 복사해서도 안 되고 정해진(고정된) 추가 공간만 사용하라.

https://leetcode.com/problems/find-the-duplicate-number/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이

set을 이용

문제에서는 정해진(고정된) 추가 공간(constant extra space)만을 사용하라고 했지만, 딱히 해당 조건을 지키는 풀이가 생각나지 않아 set을 이용해서 풀었다.

 

이렇게 풀어도 통과는 한다.

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

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums) {
            if (set.contains(num)) {
                return num;
            }
            set.add(num);
        }
        return -1;
    }
}

이진 탐색을 이용

이진 탐색을 이용하면 위의 조건 (배열을 복사하지 않고 고정된 크기의 추가 공간 사용)을 맞추면서 답을 구할 수 있다.

 

일단 이진 탐색이란 배열이 주어졌을 때, 가운데 값부터 보면서 탐색 범위를 조정해주는 방식이다. 때문에 해당 배열은 무조건 정렬되어 있어야 한다.

 

다만, 우리가 현재 풀고 있는 문제의 경우 주어진 배열이 정렬되어 있지 않다. 물론 정렬해서 앞 뒤로 같은 값을 찾아줘도 되지만, 이진 탐색을 이용하면 굳이 정렬하지 않고 문제를 풀 수 있다.

 

내가 위에서 이진 탐색에 관해 설명할 때, 배열이라고 했지만 사실 이진 탐색은 특정한 범위 안에서 조건에 맞는 값을 찾는 데에도 사용된다. 백준의 '나무 자르기' 그 예이다.

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

문제에서는 배열 안에 들어 있는 각 정수의 범위는 1부터 배열의 길이 -1인 [1, n] 이라고 설명했다. 그러므로 우리는 배열 안에 있는 정수의 범위 그 자체를 이진 탐색으로 보면서 조건에 따라 mid를 조정해 줄 것이다.

 

참고로 해당 이진 탐색은 lowerBound로 풀었다.

 

1. 일단 low와 high을 배열 안의 정수가 가질 수 있는 최솟값과 최댓값으로 정해준다. 때문에 low는 1, high는 nums.length -1이 된다.

2. low가 high 보다 작을 때까지 이진 탐색을 돌려준다.

3. mid를 (low+high)/2로 중간 값을 찾아준다. 그리고 배열을 돌면서 mid보다 작거나 같은 값을 센다. 여기서 구한 cnt는 나중에 범위를 조정할 때 사용이 된다.

4. cnt가 mid보다 작거나 같으면  low에 mid+1을 넣어서 범위를 높여준다. 왜냐하면 기준인 mid보다 작거나 같은 수가 mid 보다 작거나 같기에 값을 더 높여서 작거나 같은 수가 더 많게 나오도록 만들어줘야 하기 때문이다.

 

위에서는 mid와 작거나 같은 값을 셌다. 만일 mid가 우리가 찾는 정답일 경우 무조건 cnt가 2 이상일 것이다. 또한 중복되는 값은 오로지 하나뿐이라는 것을 기억하자. 그러므로 cnt가 mid보다 작다는 의미는 우리가 찾는 정답보다 mid가 작다는 의미이고 그렇기에 low에다가 mid + 1을 해줘서 mid의 탐색 범위를 높이는 것이다.

 

또한 cnt가 mid보다 클 때는 범위가 크다는 의미이므로 high를  mid로 넣어 더 작게 조정해줘야 한다.

 

이러한 문제를 이진 탐색으로 풀 때는 정확한 값을 한 번에 찾 것이 아니라, 특정한 기준을 가지고 계속해서 범위를 조정해나가며 low가 high보다 크거나 같게 되는 순간 존재하는 low(lowerBound일 경우)가 답이라는 걸 기억하자.

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

class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int low = 1;
        int high = len - 1;

        while (low < high) {
            int mid = (high + low)/2;
            int cnt = 0;
            for (int i=0; i<len; i++) {
                if (nums[i] <= mid) {
                    // 더 작거나 같은 걸 찾는다.
                    cnt++;
                } 
            }

            if (cnt <= mid) {
                // mid가 cnt보다 크거나 같으면 범위를 높여줌
                System.out.println("범위를 넓힌다.");
                low = mid + 1;
                System.out.println(low);
            } else {
                System.out.println("범위를 좁힌다.");
                high = mid;
                System.out.println(high);
            }
        }
        return low;
    }
}