백준 1920번[수찾기] 문제풀이

문제 설명

이진 탐색 - 수 찾기 문제

1920번 수 찾기 : 문제 설명

1920번 수 찾기 : 입출력 예시

 

📌문제 접근 방법

처음에 간단히 생각했던 방법은 '빈 리스트에 B가 A에 있으면 1, 없으면 0을 저장하자'였습니다.

1. 빈 리스트 생성

2. B가 A에 있다면 1, 없으면 0 리턴

📌1차 오답

소스코드

import sys

M = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
N = int(sys.stdin.readline().rstrip())
B = list(map(int, sys.stdin.readline().rstrip().split()))

def solution(A, B):
    res = []
    for x in B:
        if x in A:
            res.append(1)
        else:
            res.append(0)
    return res

res = solution(A,B)
for x in res:
    print(x)

제출 결과는 시간 초과였습니다.

📌문제점 분석

문제점은 리스트의 개수를 고려하지 않았다는 것입니다.

다시 살펴보니 리스트 개수인 M,N은 $10^{5}$개까지 가능합니다.

B가 $10^{5}$개, A가 $10^{5}$개일 경우 최대 $10^{10}$의 연산을 거쳐야 합니다.

각각의 B가 $10^{5}$개의 A에 속하는 지 확인해야 하기 때문입니다.

그래서 이진 탐색을 사용하면 복잡도를 낮출 수 있지 않을까? 생각했습니다.

참고로 이진 탐색을 사용하기 위해선 정렬을 수행해야 합니다.

📌2차 제출

이진 탐색을 구현한 뒤 적용하니 통과했습니다. 👏👏

1920 문제풀이 성공

소스코드

import sys

M = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
N = int(sys.stdin.readline().rstrip())
B = list(map(int, sys.stdin.readline().rstrip().split()))
# 이진 탐색을 위한 정렬
A.sort()

def binary_search(A, x):
    left, right = 0, len(A)-1

    while left <= right:
        mid = (left+right)//2
        if x == A[mid]:
            return 1
        elif x < A[mid]:
            right = mid-1
        else:
            left = mid+1
    return 0

def solution(A, B):
    res = []
    for x in B:
        num = binary_search(A, x)
        res.append(num)
    return res

res = solution(A,B)
for x in res:
    print(x)

 

📌느낀점

문제 풀이 시 주어지는 숫자에 집중해야 할 것 같습니다.

이것이 복잡도와 연결되고 사용할 수 있는 알고리즘과 없는 알고리즘이 나뉩니다.

따라서 사용할 알고리즘이 무엇인지 파악하고 접근하면 시간을 줄일 수 있으리라 생각합니다.

자주 사용하는 이진 탐색은 구현이 간단하므로 바로 구현할 수 있도록 연습해야겠습니다.