이 부분 다시리뷰 필요[python_파이썬_Pass]백준_10816번_수찾기_이분탐색_풀이

공부하는허딩크 : https://www.youtube.com/live/YUFXMQL1DWY?feature=shared

 

<첫번째 시도 : 시간초과>

이전에 2번 맞은 건 일단 넘어가고 가장 효율적인 코드라고 생각되는 방향으로 만들었다.

기존 다른 문제에서는 비슷하게 되었는데 핵심은 N_nums를 집합(set)으로 하면 되지만, count를 지원하지 않으며,

중복되는 숫자들의 개수를 구해야 하기 때문에 어차피 집합은 불가능하다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

for i in M_nums:

    print(N_nums.count(i), end = ' ')

 

<두번째 시도 : 맞았습니다.>

해시를 이용해서 풀었다.

기존에 if answer[i]: answer에 i가 있을 경우의 조건을 줬는데 딕셔너리는 else로 넘어가기 전에 i가 없으면 KeyError를 발생한다. 존재하지 않는 키로 answer[i]에 접근하려면 오류를 던진다. 따라서 존재 여부를 확인해야한다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {}

for i in N_nums:

    if i in answer: # if answer[i]: ???이게 왜??? 아.. 없을 수도 있지....

        answer[i] += 1

    else:

        answer[i] = 1

for i in M_nums:

    print(answer.get(i, 0), end = ' ')

 

※참고 라이브러리

from collections import defaultdict 라이브러리를 사용하면 키값이 없을 경우 KeyError가 발생하지 않고 기본값을 0으로 생성한다.

import sys

from collections import defaultdict

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = defaultdict(int)

for i in N_nums:

    answer[i] += 1

for i in M_nums:

    print(answer.get(i, 0), end = ' ')

 

<세번째 시도 : 시간초과>

이진탐색으로 코드를 만들었다. 단, 탐색이 동일한 요소를 찾아서 cnt +1을 해줘야 하는데 이 조건이 조금 까다롭다.

파이썬으로 실행시 1분째 답이 안나온다(기다려도 답은 나오지 않음). 백준에서는 시간초과가 나옴. (=> 그럼 답은 나온다는건가?)

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

N_nums.sort()

#[-10, -10, 2, 3, 3, 6, 7, 10, 10, 10]

def Binary(arr, m):

    start, end = 0, len(arr) - 1

    cnt = 0

   

    while start <= end:

        mid = (start + end) // 2

        if arr[mid] == m:

            cnt += 1

            if mid != 0 and mid != (len(arr) - 1):

                if arr[mid + 1] == m:

            #여기서 한번 더 생각필요

                    start = mid + 1 #오른쪽에 동일한 것들이 있음

                elif arr[mid - 1] == m:

                    end = mid -1

        elif arr[mid] > m:

            end = mid - 1

        else:

            start = mid + 1

   

    return cnt

for i in M_nums:

    print(Binary(N_nums, i), end = ' ')