본문 바로가기
DEVLOG/Algorithms

[BOJ 1920] 수 찾기 파이썬 풀이

2019. 8. 28.
반응형

 

1920번: 수 찾기

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

www.acmicpc.net

잘못된 풀이 1 - 시간 초과


def binarySearch(nums, q):
    mid = len(nums)//2
    if nums[mid] == q:
        print(1)
    elif len(nums) == 1:
        print(0)
    else:
        if q < nums[mid]:
            binarySearch(nums[:mid], q)
        else:
            binarySearch(nums[mid:], q)


N = int(input())
nums = list(map(int, input().split()))
nums.sort()
M = int(input())
Qs = list(map(int, input().split()))

for q in Qs:
    binarySearch(nums, q)

 

잘못된 풀이 2 - 런타임 에러

N = int(input())
nums = list(map(int, input().split()))
maxnum = max(nums)
M = int(input())
Qs = list(map(int, input().split()))

hashtable = [0]*(maxnum+1)

for num in nums:
    hashtable[num] = 1

for q in Qs:
    if q>maxnum or hashtable[q]==0:
        print(0)
    else:
        print(1)

 

잘못된 풀이 3 - 시간 초과

N = int(input())
nums = list(map(int, input().split()))
maxnum = max(nums)
M = int(input())
Qs = list(map(int, input().split()))

hashtable = {}

for num in nums:
    index = num%10
    if index in hashtable:
        hashtable[index].append(num)
    else:
        hashtable[index] = [num]

for q in Qs:
    index = q%10
    found = 0
    if index in hashtable:
        for h in hashtable[index]:
            if h == q:
                found = 1
    print(found)

 

맞은 풀이

N = int(input())
nums = list(map(int, input().split()))
M = int(input())
Qs = list(map(int, input().split()))

hashtable = {}

for num in nums:
    index = num%10
    if index in hashtable:
        hashtable[index].append(num)
    else:
        hashtable[index] = [num]

for q in Qs:
    index = q%10
    found = 0
    if index in hashtable:
        for h in hashtable[index]:
            if h == q:
                found = 1
    print(found)

 

반응형

댓글