백준 1920번 수 찾기 문제풀이, 파이썬

백준 1920번 : 수 찾기 문제풀이 [파이썬] 

---

<문제>

 

1920번 문제의 내용은 아래와 같습니다. 

 

 

수 찾기

문제

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 복사

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

---

 

 

<작성한 코드>

 

def binary(arr, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if arr[mid] == target:
      return True
    elif arr[mid] > target:
      end = mid - 1
    else:
      start = mid + 1


N = int(input())
list_N = list(map(int, input().split()))
list_N.sort()
M = int(input())
list_M = list(map(int, input().split()))

for i in list_M:
  if binary(list_N, i, 0, N-1):
    print(1)
  else:
    print(0)

---

 

 

<코드 풀이>

 

처음에 이 문제는 정말 간단하게 코드를 작성하고 제출했다. 

import sys

N = int(input())
list_N = list(map(int, sys.stdin.readline().split()))
M = int(input())
list_M = list(map(int, sys.stdin.readline().split()))

for i in list_M:
  if i in list_N:
    print(1)
  else:
    print(0)

위와 같은 코드를 제출해서 문제가 원하는 결과값을 얻기는 했으나

결과는 시간초과....

문제에 주어진 시간 제한이 1초였다.

그래서 귀찮았지만 이분 탐색(이진 탐색)을 사용해서 문제를 풀기로 했다. 

 

2023.03.14 - [백준 알고리즘] - [알고리즘] 이진 탐색 알고리즘(1)

[알고리즘] 이진 탐색 알고리즘(1)

 

 

 

우선 이분 탐색을 사용하기 전에 문제에서 주어진 입력값들을 

입력하는 부분이 필요해서 다음과 같이 작성해주었다. 

N = int(input())
list_N = list(map(int, input().split()))
list_N.sort()
M = int(input())
list_M = list(map(int, input().split()))

여기서 list_N.sort() 를 사용해 리스트를 오름차순 정렬을 해주었음을 알 수 있는데,

이분 탐색을 사용하려면 그 전에 리스트들을 정렬한 상태에서 사용해야하기 때문이다. 

 

 

 

def binary(arr, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if arr[mid] == target:
      return True
    elif arr[mid] > target:
      end = mid - 1
    else:
      start = mid + 1

 

다음으로 이분 탐색을 실행하기 위한 함수를 위와 같이 작성해주었다.

함수의 인수로는 (리스트, 찾아야하는 값, 시작 인덱스, 끝 인덱스) 를 받아주었다. 

 

 

 

for i in list_M:
  if binary(list_N, i, 0, N-1):
    print(1)
  else:
    print(0)

결과 값을 출력해주는 부분은 위와 같다. 

list_M 안에 있는 숫자들을 하나씩 돌면서 

만약 우리가 정의한 함수를 실행했을때, 

True가 나온다면 값이 존재하는 것이기 때문에 print(1)을 통해 1을 출력하고

아니라면 0을 출력하도록 작성해주었다 .