백준 1920 - 수 찾기

nowkim·2021년 5월 4일
0

코딩테스트

목록 보기
1/7
post-thumbnail

첫 번째 코드

def Find(arr,target):
    # 1번씩 다 비교하면서 출력해도 됨
    # but 이진탐색으로 출력해보자

    low = 0
    high = N
    mid = (high + low) // 2

    while low < high:
        # 이진탐색 시작, 중간값으로 대소비교
        if arr[mid] > target:
            high = high -1
            mid = (high + low) // 2
        elif arr[mid] < target:
            low = low + 1
            mid = (high + low) // 2
        else:
            # arr[mid] == target, 값을 찾음
            return 1
        
        #break point -> index를 벗어남. (찾는값이 없음)
        if low > high:
            return 0
    
    # while 안에서 못찾았으면 무조건 not found.
    return 0

N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))

for target in M_list:
    # M_list[i]가 A에 있는지 없는지 찾는 함수, 있으면 1, 없으면 0 리턴
    print(Find(A,target))

결과 : 시간 초과


두 번째 코드

def Find(arr,target,low,high):
    
    if high < low:
        return False
    
    mid = (high + low) // 2

    if arr[mid] > target:
        return Find(arr,target,low,high-1)
    elif arr[mid] < target:
        return Find(arr,target,low+1,high)
    else:
        return True
    

N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))

for target in M_list:
    # M_list[i]가 A에 있는지 없는지 찾는 함수, 있으면 True, 없으면 False 리턴
    if Find(A,target,0,N-1):
        print(1)
    else: 
        print(0)

결과 : 런타임 에러

런타임 에러가 발생하는 일반적인 이유?

  • 배열에 할당된 크기를 넘어서 접근했을 때
  • 전역 배열의 크기가 메모리 제한을 초과할 때
  • 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
  • 0으로 나눌 떄
  • 라이브러리에서 예외를 발생시켰을 때
  • 재귀 호출이 너무 깊어질 때
  • 이미 해제된 메모리를 또 참조할 때
  • 프로그램(main 함수)이 0이 아닌 수를 반환했을 때

출처 : https://www.acmicpc.net/board/view/22980


세 번째 코드

수정사항 - Find함수 안에서 재귀로 호출할 때 index를 좀 더 효율적으로 주었다.

def Find(arr,target,low,high):
    
    if high < low:
        return False
    
    mid = (high + low) // 2

    if arr[mid] > target:
        return Find(arr,target,low,mid-1)
    elif arr[mid] < target:
        return Find(arr,target,mid+1,high)
    else:
        return True
    

N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))

for target in M_list:
    # M_list[i]가 A에 있는지 없는지 찾는 함수, 있으면 True, 없으면 False 리턴
    if Find(A,target,0,N-1):
        print(1)
    else: 
        print(0)

결과 : 성공 !

profile
끙끙대며 배우는 중

0개의 댓글