[BoJ][Python] 암기왕

목차

🫡 Overview

체감 난이도: ★☆☆☆☆

소요시간: 

문제 레벨:  실버4 / 문제 유형: 이분탐색
풀이 상태:  스스로 해결
추후: 완벽 이해

 

---

문제 링크

https://www.acmicpc.net/problem/2776

요구사항 분석

"""
문제: 수첩2에 있는 모든 수 들이 수첩 1에 있는지 찾기
output: 있으면 1, 없으면 0

## 알고리즘
완전 탐색
- 수첩 2에 있는 모든 수들에 대해서, 수첩 1의 숫자들과 숫차 비료
- O(M*N) = O(1,000,000* 1,000,000) => 시간 초과

이분 탐색 알고리즘 적용 시
- 수첩 1에 있는 숫자 정렬 O(NlogN)
- 수첩 1의 데이터 셋에서 수첩 1의 1개의 숫자를 찾기: O(logN)
- 수첩 2의 모든 숫자를 찾기 : O(M*logN) =  10**6 x 6*log10
  - 18,000,000 => 약 2천만 연산으로 처리 가능
"""

 

나의 코드

T = int(input()) # 테스트 케이스 개수

for _ in range(T):
    N = int(input()) # 정수의 개수 1 <= N <= 1,000,000
    N_lst = list(map(int, input().split()))
    M = int(input()) # 수첩 2의 정수 개수: 1 <= N <= 1,000,000
    M_lst = list(map(int, input().split()))


    def binary_search(target, N_lst):
        left, right = 0,len(N_lst)-1

        while left<=right:
            mid = (left+right)//2
            #print('left mid right :', left, mid, right)
            if N_lst[mid] == target:
                #print("타겟을 찾음")
                return 1
            elif N_lst[mid] < target:
                #print("target이 mid 보다 오른쪽 영역에 있음, left는 ")
                left = mid + 1
            else:
                #print("target이 mid 왼쪽 영역에 있음 ")
                right = mid - 1
        return 0

    # 리스트 정렬
    N_lst.sort()

    # 요소 찾기
    result = []
    for m in M_lst:
        result.append(binary_search(m, N_lst)) # 있으면 True, 아니면 false
    print('\n'.join(map(str, result)))

 

---

 

 

#백준 #코딩테스트 #알고리즘 #python #파이썬