문제: 수 찾기

• 문제
  • N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
• 입력
  • 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
• 출력
  • M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

풀이1. 시간복잡도가 높은 잘못된 풀이

# input 값
N = 5
N_list = [4, 1, 5, 2, 3]
M = 5
M_list = [1, 3, 7, 9, 5]

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

for item in M_list:
    if item in N_list:
        print(1)
    else:
        print(0)
"""        
1
1
0
0
1
이 출력된다.
"""

이 코드는 두 개의 리스트(N_list와 M_list)를 비교하여 M_list에 있는 각 요소가 N_list에 포함되어 있으면 1을, 포함되어 있지 않으면 0을 출력한다.

코드의 작동 단계는 다음과 같다.

• 입력 받기
  • 첫 줄에 정수 N을 입력받습니다. 이것은 N_list의 요소 수를 나타낸다.
  • 두 번째 줄에는 N개의 정수를 입력받아 N_list에 저장한다.
  • 세 번째 줄에 정수 M을 입력받습니다. 이것은 M_list의 요소 수를 나타낸다.
  • 네 번째 줄에는 M개의 정수를 입력받아 M_list에 저장한다.
• 정적 값 할당
  • input에 값을 할당한다.
• 탐색 및 출력
  • M_list의 각 요소에 대해서, 해당 요소가 N_list에 포함되어 있는지 확인한다.
  • 만약 포함되어 있다면 1을 출력하고, 그렇지 않으면 0을 출력한다.

풀이 2.

# input 값
N = 5
N_list = [4, 1, 5, 2, 3]
M = 5
M_list = [1, 3, 7, 9, 5]

N_list.sort()
def binary_search(data, search):
    if len(data) == 0:
        return 0
    elif len(data) == 1:
        if data[0] == search:
            return 1
        else:
            return 0
    
    medium = len(data) // 2
    if search == data[medium]:
        return 1
    else:
        if search > data[medium]:
            return binary_search(data[medium+1:], search)
        else:
            return binary_search(data[:medium], search)
        
for item in M_list:
    print(binary_search(N_list, item)) 

이 코드는 이진 탐색 (Binary Search) 방법을 이용하여 주어진 리스트(N_list)에서 특정 원소(item in M_list)가 존재하는지를 찾아내는 것이다.

코드의 흐름은 다음과 같다.

1. 'N_list'를 먼저 오름차순으로 정렬한다.
2. 이진 탐색 함수 'binary_search'를 정의한다.
3. 각 item in M_list에 대해 binary_search 함수를 호출하여 해당 원소가 N_list에 존재하는지 확인한다.

이진 탐색 함수의 작동 방식

• 주어진 data가 비어 있다면, 찾고자 하는 search는 없는 것이므로 0을 반환한다.
• data에 원소가 하나만 있다면, 그 원소가 찾고자 하는 search와 동일한지 확인하고, 동일하다면 1을, 그렇지 않다면 0을 반환한다.
• 위의 두 경우가 아닌 경우, data의 중앙값과 search를 비교한다.
  • search가 중앙값보다 크다면, data의 오른쪽 절반에 대해 이진 탐색을 재귀적으로 수행한다.
  • search가 중앙값보다 작다면, data의 왼쪽 절반에 대해 이진 탐색을 재귀적으로 수행한다.

마지막으로, 각 item in M_list에 대해 이진 탐색 함수를 호출하여 결과(1 또는 0)를 출력한다. 여기서 1은 해당 원소가 N_list에 존재함을, 0은 존재하지 않음을 나타낸다.