[백준] 1920 수 찾기 python 알고리즘 문제

문제 1920. 수 찾기

1. 나의 코드와 발상 과정

import sys

n = int(input())
num_list = list(map(int, sys.stdin.readline().split()))
m = int(input())
find_list = list(map(int, sys.stdin.readline().split()))

num_list.sort()

def count_by_range(array, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if array[mid] == target:
        return 1
    elif array[mid] > target:
        return(count_by_range(array, target, start, mid - 1))
    else:
        return(count_by_range(array, target, mid + 1, end))

for i in find_list:
    print(count_by_range(num_list, i, 0, n - 1))

10816번 숫자 카드 2 문제와 같다.

이진 탐색을 활용하는 방법이며, n의 범위가 크기 때문에 이차 시간을 복잡도로 가지는 코드는 사용할 수 없다.

 

def는 return이 0 또는 1만 나올 수 있는 재귀함수로 구성하였다.

시작점이 end보다 크면, 탐색된 값이 없기 때문에, 0을 리턴한다.

target으로 설정한 찾고자 하는 수가 mid값과 같다면, 그 수를 찾은 것이기 때문에 1을 리턴한다.

 

10816번은 카드의 수를 세는 것이지만, 이 문제는 있는지 없는지 여부만 확인하면 되기에,

매개변수가 총 4개이다. 이 문제를 나중에 풀었기 때문에 간단히 풀이할 수 있었다.

 

 

2. 아쉬운 점

재귀함수를 구현할 때 아직 머리에 잘 그려지지 않는 점이 아쉽다.

직접 손으로 그려가면서 해보는 것이 제일 이해가 잘 되니 당분간은 그렇게라도 빡세게 구상해야 할 듯 하다.

 

 

 

문제 출처:

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