[백준] 수찾기 1920.python

Java가 주 언어이므로 Python을 공부할 겸 Python으로 문제를 풀었다.

따라서, Python 문법에 대한 설명이 포함되어 있다.

 문제

- N개의 숫자 배열(arr)을 입력받았을 때, 각각의 숫자(총 M개)가 arr 배열에 포함이 되는지를 묻는 문제이다.

- 배열을 모두 탐색하면서 숫자가 존재하는 지를 반복문을 통해 찾으면 된다고 생각했지만, 그러면 시간초과 오류가 난다!

 해설 및 코드

- for문을 이용하여 탐색하면 O(N)의 시간이 걸린다.

- 이진탐색은 O(logN)의 시간이 걸리므로 for문으로 탐색하는 것보다 더 적은 시간이 걸린다.

- 하지만 이진 탐색 전에 반드시 탐색할 배열을 sort 해줘야 한다. 안하면은 절반으로 나누면서 가는 이유가 없잖아?

# bs 함수 - 이진탐색
# low, high, num을 인자로 받음
# 각 인자들은 int 형으로 넘어온다. 아마도?
def bs(low, high, num):

    # low가 high 보다 커지게 되면 해당되는 숫자가 배열 안에 존재하지 않음
    if(low > high):
        return 0

    # int 형으로 바꿔주지 않으면 mid를 str로 인식한다.
    mid = int((low + high) / 2)

    # 존재한다면 1을 return한다.
    if(arr[mid] == num):
        return 1

    # 현재 mid의 숫자가 num 보다 크면 high를 mid-1로 정의하여 재귀
    if(arr[mid] > num):
        return bs(low, mid-1, num)

    # 현재 mid의 숫자가 num 보다 작으면 low를 mid+1로 정의하여 재귀
    return bs(mid+1, high, num)

# --------- main ----------

# int형 한 개를 입력받을 때
N = int(input())

# int형으로 여러 개를 입력받아 list 형식으로 저장할 때(배열)
arr = list(map(int,input().split()))

M = int(input())
num = list(map(int, input().split()))

# 배열 정렬 - 오름차순
arr.sort()

# 반복문
# 배열 num에 담긴 숫자들은 m이 되어 반복된다.
# ex) num = {1, 5, 8, 6} 이면, m은 1 -> 5 -> 8 -> 6 순서로 접근한 후 반복문 종료
for m in num:
    print(bs(0, N-1, m)) # bs 함수 시작

어디선가 블로그를 참고해서 java로 풀었던 것을 python으로 바꿨다.

mid가 str로 잡히는 이유를 몰라서 계속 에러를 만났던 것 같다.

python은 역시 어렵다..

 

Python 문법 정리

1. 입력

  - 한 줄 입력 (Enter 구분)

input()

int(input())					# 입력받은 str을 int형으로 변환

  - list로 입력

list(input().split())					# str형의 list 입력

list( map(int, input(),split() )			# int형의 list 입력

 

2. List

  - List 정렬

list.sort()				# 오름차순
list.sort(reverse = True) 		# 내림차순