[Baekjoon] 1920번 수 찾기

수 찾기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	144337	42361	28072	29.884%

문제

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

문제 풀이

1. for문과 if문으로 그냥 푸는 코드
2. linear search를 하는 코드
3. binary search를 하는 코드
4. bisect를 사용한 코드

이 때 중요한 점은 binary search의 경우 sort를 해야만 하기 때문에 이 과정을 추가하는데 이는 시간 복잡도에 영향을 미치지 않는다.

for문과 if문의 조합으로 탐색: 시간 초과

import sys
import bisect

N = int(input())

card = list(map(int, input().split()))
card.sort()
M = int(input())
target = list(map(int, input().split()))


for j in target:
    if j in card:
        print(1)

    else:
        print(0)

for문과 if문의 조합으로 탐색하게 되면 시간 초과가 발생하게 된다.

따라서 searching 알고리즘 중에 한 방법을 사용하여 풀어야 한다.

linear search를 하는 코드: 시간 초과

# 1. Linear Search
import sys


def search(card, target):
    card_size = len(card)

    for j in range(card_size):
        if target == card[j]:
            print(1)
            return
    print(0)
    return



N = int(input())
_card = list(map(int, input().split()))

M = int(input())
_target = list(map(int, input().split()))

for i in _target:
    search(_card, i)

linear search는 사실상 시간 복잡도 측면에서 유리한 점이 없기 때문에 유사하기 앞 코드와 별 다를 바 없이 시간 초과가 발생한다.

binary search를 하는 코드

# 2. Binary search
import sys


def binarysearch(card, target):
    left, right = 0, len(card) - 1

    while left <= right:
        mid = (left + right) // 2

        if target < card[mid]:
            right = mid - 1
        elif target > card[mid]:
            left = mid + 1
        else:
            print(1)
            return

    print(0)
    return



N = int(input())
_card = list(map(int, input().split()))
_card.sort()

M = int(input())
_target = list(map(int, input().split()))

for i in _target:
    binarysearch(_card, i)

이진 탐색을 사용하여 푼 결과 시간 초과가 발생하지 않고 풀 수 있었다.

bisect 라이브러리를 사용한 코드

# 3. Using bisect module
import sys
import bisect


def bisectsearch(card, target):
    index = bisect.bisect_left(card, target)
    if index < len(card) and card[index] == target:
        print(1)
        return
    else:
        print(0)
        return



N = int(input())
_card = list(map(int, input().split()))
_card.sort()

M = int(input())
_target = list(map(int, input().split()))

for i in _target:
    bisectsearch(_card, i)

또한 파이썬에는 bisect라는 모듈이 존재하는데 이를 사용하여 푼 결과 binary search 보다 더 빠른 시간 안에 풀 수 있었다.

이렇듯 이미 존재하는 모듈을 활용하여 풀면 더 시간 단축을 할 수 있으므로 여러 모듈을 적재적소에 사용할 수 있는 것이 중요하다.