[백준] 1920.수 찾기

문제 바로가기

문제 풀이

nums로 숫자 값을 받은 뒤 그 안에 들어있는지 탐색
1. 그냥 단순 구현 : in nums로 check했더니 시간초과 발생 ( list 내의 모든 값을 서치하는 데에 시간이 오래 걸림 ) list에서의 탐색 함수의 시간 복잡도는 O(n)
2. 이분탐색을 이용 : l,r값을 지정한 후 sorted(nums)에서 인덱스를 이용한 크기 비교를 통해 l, r 값을 업데이트하며 비교 -> 통과
3. set을 이용 : nums를 set로 받은 후 search할 때의 시간 복잡도 함수는 O(1)로 list에서의 탐색보다 훨씬 빠른 속도를 가짐 -> 통과

정답 코드

# 2번 코드
"""
https://www.acmicpc.net/problem/1920
"""
import sys

input = sys.stdin.readline
N = int(input())
nums = sorted(map(int, input().split()))
M = input()
check = map(int, input().split())
for i in check:
    l, r = 0, N - 1  # 이분탐색 초기 설정값
    find = False

    # 이분탐색 시작
    while l <= r:  # l이 r과 커지면 정지
        mid = (l + r) // 2
        if i == nums[mid]:
            find = True
            print(1)
            break
        elif i > nums[mid]:
            l = mid + 1
        else:
            r = mid - 1
    if not find:
        print(0)

############################################
# 3번 코드
"""
https://www.acmicpc.net/problem/1920
"""
import sys

input = sys.stdin.readline
N = int(input())
nums = set(map(int, input().split()))
M = input()
check = map(int, input().split())
for i in check:
    print(1) if i in nums else print(0)

추가적인 개념 (optional)

set에서의 탐색 함수의 시간 복잡도는 O(1)로 list의 이분탐색보다 성능이 더 좋다.
각 함수의 시간 복잡도를 알고 최적의 함수를 이용하는 것이 골드 문제 풀 때 많이 도움 된다. ( 답은 맞지만 시간 초과로 통과하지 못하는 경우가 매우 많음...😢