[BOJ/python] 2776번 암기왕

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

2776번: 암기왕

 

문제 해석

 

간단히 수첩 2에 적혀 놓은 정수가 수첩 1에 적혀 있는지 찾는 문제이다.

---

코드

input = __import__('sys').stdin.readline
t = int(input())
for k in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    m = int(input())
    isIn = list(map(int, input().split()))

    arr = sorted(arr)
    for i in isIn:
        s = 0
        e = n - 1
        flag = True
        while s <= e:
            mid = (s + e) // 2
            if arr[mid] == i: 
                print(1)
                flag = False
                break
            elif arr[mid] < i:
                s = mid + 1
            else:
                e = mid - 1
        if flag: print(0)

---

문제 풀이

 

들어가는 수의 범위는 int형의 범위이고,  정수의 개수는 1,000,000 이므로 일반적인 탐색 방법으로는 시간초과가 난다.따라서 이분탐색을 통해 문제를 풀어주면 된다.수첩2의 적힌 배열들이 수첩1에 적혀 있는지 이분 탐색을 통해 확인하고, 없다면 flag == True로 0을 출력하고, 있다면 1을 출력하면 되는 간단한 문제이다.

 

이 문제에는 T의 테스트 케이스를 받아서 1번 이상 진행한다. 문제를 잘 보고 풀어야 할 것 같다.

 

 

원문

https://ddingmin00.tistory.com/28