[백준] 1920번 : 수 찾기

1920번: 수 찾기

1920번: 수 찾기

📄 문제개요

• N개의 정수 A[1], A[2], …, A[N]이 주어져 있을때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
• M개의 쿼리가 주어졌을때 해당 쿼리가 존재하면 1 존재하지 않으면 0을 출력하시오.
• 1≤ N ≤ 100,000, 1 ≤ M ≤ 100,000 -2^31 ≤ A[i] ≤ 2^31

🤔 문제분석

• O(N*M)으로 완전탐색으로 해당값이 있는지 탐색 할 수 있다.
• 하지만 100,000 * 100,000 임으로 원하는 시간내에 해결 할 수 없다.
• 정렬을 한뒤 O(Nlog(N)), 이분탐색으로 값이 있는지 없는지 탐색 할 수 있다. O(Mlog(N))
• 총 시간복잡도 : O(Nlog(N) + O(Mlog(N))

📝 의사코드

1. 입력받은 배열을 정렬한다.
2. 입력받은 쿼리를 순회하면서 해당쿼리를 이분탐색으로 값이 있는지 없는지 존재한다.
3. 이분탐색은 start = 0 , end = 배열의길이-1 로 시작하여 A[mid] 값에 따라서 분기한다.
   1. A[mid]값이 쿼리와 같은경우 탐색을 멈추고 존재한다고 출력한다.
   2. A[mid]값이 쿼리보다 클경우 왼쪽 범위를 탐색한다. end = mid - 1
   3. A[mid]값이 쿼리보다 작을경우 오른쪽 범위를 탐색한다. start = mid + 1

💻 코드

import sys
input = sys.stdin.readline

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

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

# 숫자를 정렬한다 O(Nlog(N))
num.sort()

def find_num(arr, query):
    start = 0
    end = len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        
        if arr[mid] == query:
            return 1
        elif arr[mid] > query:
            end = mid - 1
        else:
            start = mid + 1
    
    return 0
    
for query in queries:
    print(find_num(num, query))

🎯 피드백 및 개선사항

• 이분탐색을 학습중이라 문제를 쉽게 풀 수 있었습니다.
• 다른사람이 어떻게 풀었을까 검색해보니 집합자료형을 사용하여 문제를 해결한 문제가 보여 해당 문제로 풀어보았습니다.

❓다른사람은 어떻게 풀었을까?

[Python] 백준 1920번 수 찾기 - 두가지 풀이:이분탐색과 자료형

[Python] 백준 1920번 수 찾기 - 두가지 풀이:이분탐색과 자료형

• 집합자료형으로 num 자료형을 초기화 시켰고, 해당 값이 query에 있는경우 1 그렇지 않은경우 0으로 문제를 해결 할 수 있습니다.
• 훨씬 코드가 간결하고, O(M)의 시간복잡도로 해당문제를 해결 할 수 있습니다.

import sys
input = sys.stdin.readline

N = int(input())
num = set(list(map(int, input().split())))

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

for query in queries:
    if query in num:
        print(1)
    else:
        print(0)