[Prgrammers] 입문) 가까운 수 (이진탐색)

 

이번 문제는 간단한 이진탐색 문제였다.

 

우선 문제에서 주의할 점은 예제의 배열들은 순서대로 나오지만 실제 테스트 배열들이 순서대로 나올지는 미지수라는 것이다.

그렇기에 일단 배열을 정렬하고 이진탐색을 통해 답을 찾을 것이다.

 

주요 포인트)

1. 배열 정렬

2. 이진탐색을 통해 주어진 값이 어떤 수 사이에 들어갈지 확인하는 로직

3. 이진 탐색 전 예외처리

 

solution(배열, 목표값)
	배열을 오름차순으로 정렬
    목표값이 배열의 범위를 벋어나는 숫자인지 확인
    이진탐색으로 목표값이 배열의 어느자리에 들어갈지 확인

using System;
using System.Linq;

public class Solution {
    public int solution(int[] array, int n) {
        int position = array.Length / 2;
        int start = 0;
        int end = array.Length - 1;
        
        Array.Sort(array);
        
        // 양 끝점 확인
        if (array[0] >= n) return array[0];
        if (array[array.Length - 1] <= n) return array[array.Length - 1];
        
        for (int k = 0; k < array.Length / 2; k++){
            // 현재 원소가 목표값과 같다면 반환
            if (array[position] == n)
                return array[position];
            
            // 현재 원소가 목표값보다 크면 실행
            if (array[position] > n) {
                // 현재 원소 바로 아래 원소와 비교
                if (array[position - 1] == n)
                    return array[position - 1];
                
                // 목표값이 현재 원소와 아래 원소 사이라면 두 원소 중 하나가 정답
                if (array[position - 1] < n) {
                    // 현재 원소와 목표값의 차이와 아래 원소와 목표값의 차이 비교
                    if (array[position] - n < n - array[position - 1])
                        return array[position];
                    else
                        return array[position - 1];
                }
                
                end = position;
                position -= (end - start) / 2;
                continue;
            }
            
            if (array[position] < n) {
                if (array[position + 1] == n)
                    return array[position + 1];
                
                if (array[position + 1] > n) {
                    if (array[position + 1] - n < n - array[position])
                        return array[position + 1];
                    else
                        return array[position];
                }
                
                start = position;
                position += (end - start) / 2;
            }
        }
        
        return 0;
    }
}

 

아주 만족스러운 결과가 나왔다.

문제를 해결하며 잘못 생각했던 부분은 이진탐색 중 다음 위치를 정하는 부분을 안일하게 작성하였다.

 

다음 예제를 통해 확인하자.

 

[1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12], 8
위와 같은 예시가 주어졌을때 순차적 탐색 위치는 다음과 같다.

1. 6번을 기준으로 앞뒤를 확인한다.
2. 배열 뒤쪽으로 이동하는 수식으로 새로운 위치를 배정 받는다.
3. 10번을 기준으로 앞뒤를 확인한다.
4. 배열 앞쪽으로 이동하는 수식으로 새로운 위치를 배정 받는다.
5. 7번을 기준으로 앞뒤를 확인한다.
6. 주어진 값이 할당될 수 있는 위치이다.
7. 7과 9중 8과 더욱 가까운 값을 확인한다. 만약 거리가 동일하다면 더 작은 수를 반환한다.

잘못된 예시 방식 {
    // 배열 앞쪽으로 이동할 경우
    position = position / 2;
    // 배열 뒤쪽으로 이동할 경우
    position = array.Length - ((array.Length - position) / 2);
}

최종 수정한 방식 {
	int start = 0;
    int end = array.Length - 1;
    
    // 배열 앞쪽으로 이동할 경우
    end = position;
    position -= (end - start) / 2;
    // 배열 뒤쪽으로 이동할 경우
    start = position;
    position += (end - start) / 2;
}

위 예제에서 잘못된 방식을 넣어버리면 현재 위치에서 이동하는 것이 아닌 이전 기준점의 영향을 받아버린다.

 

여기서 중요한 키포인트는 매번 위치 값을 변경할때 기존 위치값에서 일정 값을 더하거나 빼는 것이다.

잘못된 방식처럼 현재 위치 값만으로는 다음 위치 값을 연산할 수 없다.