[python] 백준 1920번

안녕하세요 !

오늘은 백준 1920번 - 수 찾기 문제를 가지고 왔습니다.

문제 설명

해결 방법

첫 번째 방법

시간복잡도를 고려하기 전에는 in을 사용해서 배열 안을 검사하는 방법으로 시도했는데 시간 초과가 떠서 이진 탐색으로 풀었습니다.

in을 사용한 배열 연산 시간복잡도는 O(N)이고 이진 탐색의 시간복잡도는 O(logN)입니다.

문제를 해결한 방법은 다음과 같습니다.

1. 입력을 받는다
2. 이진 탐색을 이용해서 탐색에 성공하면 1을, 실패하면 0을 출력한다.

1. 입력을 받는다

n = int(input())
arr = list(map(int, sys.stdin.readline().strip().split()))
m = int(input())
arr2 = list(map(int, sys.stdin.readline().strip().split()))

2. 이진 탐색을 이용해서 탐색에 성공하면 1을, 실패하면 0을 출력한다.

arr.sort()
for a in arr2:
    start = 0
    end = len(arr) - 1
    exist = False
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == a:
            exist = True
            print(1)
            break
        elif arr[mid] > a:
            end = mid - 1
        else:
            start = mid + 1
    if not exist:
        print(0)

두번째 방법

이진 탐색보다 효율적인 탐색 방법은 set을 사용하는 것이다. set을 탐색하는 시간복잡도는 O(1)이다.

문제를 해결한 방법은 다음과 같다.

1. 입력을 받는다. 수를 검사할 배열은 집합 자료형으로 바꾼다.
2. 반복문을 통해 수가 있는지 검사한다.

1. 1. 입력을 받는다. 수를 검사할 배열은 집합 자료형으로 바꾼다.

n = int(input())
arr = set(map(int, sys.stdin.readline().strip().split()))
m = int(input())
arr2 = list(map(int, sys.stdin.readline().strip().split()))

2. 반복문을 통해 수가 있는지 검사한다.

for a in arr2:
    print(1) if a in arr else print(0)

결과는 다음과 같습니다.

전체 코드

첫번째 방법

import sys

n = int(input())
arr = list(map(int, sys.stdin.readline().strip().split()))
m = int(input())
arr2 = list(map(int, sys.stdin.readline().strip().split()))

arr.sort()
for a in arr2:
    start = 0
    end = len(arr) - 1
    exist = False

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == a:
            exist = True
            print(1)
            break
        elif arr[mid] > a:
            end = mid - 1
        else:
            start = mid + 1

    if not exist:
        print(0)

두번째 방법

import sys

n = int(input())
arr = set(map(int, sys.stdin.readline().strip().split()))
m = int(input())
arr2 = list(map(int, sys.stdin.readline().strip().split()))

for a in arr2:
    print(1) if a in arr else print(0)