[백준 Python Swift] 1920번 수 찾기

1920번 수 찾기

• 문제바로가기

풀이 방법

• 이분탐색으로 찾는 방법도 있고(그냥 탐색하면 $O(n)$, 이분탐색은 $O(logn)$)
• 이분탐색으로 풀땐 PyPy3로 제출하면 통과할 수 있다
• 해쉬 개념을 이용해 Set을 사용하는 방법도 있다
• 이 문제는 단순이 데이터가 배열에 있는지 없는지의 여부만 판단하면 되므로
• 중복이 허용되지 않는 set을 사용하면 좋다

---

풀이

Python

• 이분탐색을 이용한 풀이

n = int(input())
a_li = list(map(int, input().split(" ")))
m = int(input())
m_li = list(map(int, input().split(" ")))

a_li.sort() # 이분탐색시 정렬은 필수!
for i in m_li:
    medium = len(a_li) // 2
    temp_a_li = a_li
    while True:
        if len(temp_a_li) == 0:
            print(0)
            break
        elif len(temp_a_li) == 1:
            if i != temp_a_li[0]:
                print(0)
                break
        if i == temp_a_li[medium]:
            print(1)
            break
        elif i < temp_a_li[medium]:
            temp_a_li = temp_a_li[:medium]
            medium = len(temp_a_li) // 2
        elif i > temp_a_li[medium]:
            temp_a_li = temp_a_li[medium:]
            medium = len(temp_a_li) // 2

• set을 이용한 풀이

n = int(input())
a_li = set(map(int, input().split(" ")))
m = int(input())
m_li = list(map(int, input().split(" ")))

for i in m_li:
    if i not in a_li:
        print(0)
    else:
        print(1)

Swift

• set을 이용한 풀이

let n = readLine()!
let setA = Set(readLine()!.split(separator: " "))
let m = readLine()!
let setM = readLine()!.split(separator: " ")

for i in setM {
    if setA.contains(i) {
        print(1)
    } else {
        print(0)
    }
}