백준 - 10815 숫자 카드 [이분탐색]

 

10815번: 숫자 카드

 

1. 문제 요약

숫자 배열이 주어지고, 찾고자 하는 숫자가 주어졌을 때, 찾고자 하는 숫자가 배열에 존재하는지 판단하시오.

 

2. 접근 방법

이분 탐색 알고리즘을 사용합니다.

해당 알고리즘은 일반적으로 하는 up down 게임과 같은 원리입니다.

정렬된 상태에서 절반씩 소거하며 찾아내는 방법입니다.

 

오름차순으로 정렬된 배열에서 중간 부분을 탐색하고,

찾고자 하는 숫자보다 크면 해당 지점부터 끝부분까지의 중간 부분을 탐색합니다.

찾고자 하는 숫자보다 작으면 이전에 탐색했던 부분의 절반 아랫부분을 탐색합니다.

위 과정을 반복하여 찾아내는 방법입니다.

 

• 숫자 배열을 오름차순으로 정렬합니다.
• 배열의 중간 지점을 방문합니다.

 

• 찾으려는 숫자보다 클 경우, 해당 숫자를 포함하여 아랫부분은 제외하고 다시 중간 지점을 방문합니다.

 

• 찾으려는 숫자보다 작을 경우, 해당 숫자를 포함하여 윗부분은 제외하고 다시 중간 지점을 방문합니다.

 

• 위 과정을 더 이상 반복할 수 없을때까지 반복하고, 숫자를 찾으면 종료합니다.

 

3. 파이썬

def solution(n, cards, m, nums):
    cards.sort()

    for num in nums:
        s = 0
        e = n - 1
        isFind = False
        while s <= e:
            index = (s + e) // 2
            # up
            if num > cards[index]:
                s = index + 1
            
            # down
            elif num < cards[index]:
                e = index - 1
                
            # answer
            else: # num == cards[index]:
                isFind = True
                break

        if isFind:
            print('1', end=' ')
        else:
            print('0', end=' ')

 

4. 자바

private static void solution(int n, int[] cards, int[] nums) {
    Arrays.sort(cards);
    StringBuilder answer = new StringBuilder();

    for (int num : nums) {
        int s = 0;
        int e = n - 1;
        boolean isFind = false;

        while (s <= e) {
            int index = (s + e) / 2;

            if (num > cards[index]) { // up
                s = index + 1;

            } else if (num < cards[index]) { // down
                e = index - 1;

            } else { // answer
                isFind = true;
                break;
            }
        }

        answer.append(isFind ? "1 " : "0 ");
    }

    System.out.println(answer);
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/10815.%E2%80%85%EC%88%AB%EC%9E%90%E2%80%85%EC%B9%B4%EB%93%9C