[백준 10816번] 숫자 카드2 - 파이썬

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

💡문제 분석 요약

상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

💡알고리즘 설계

1. 이분 탐색 방법
중복된 값이 있을 때 그 값이 제일 앞에 있는 위치와 제일 뒤에 있는 위치를 구하는 함수를 만들고, 위치의 차를 출력한다.
upperBound 구하기: 이분 탐색을 하다가 탐색값이 타겟과 일치하거나 작은 경우 lo를 mid+1로 설정하고, lo가 hi보다 커지면 lo를 리턴한다.
lowerBound 구하기: 이분 탐색을 하다가 탐색값이 타겟과 일치하거나 큰 경우 hi를 mid-1로 설정하고, lo가 hi보다 커지면 lo를 리턴한다.
 
upperBound 함수와  lowerBound 함수의 원리가 잘 이해가 안가서 간단하게 예시 하나만 들어서 그려보았다.

 
2. 해시를 사용하는 방법
해시맵을 만들고, 숫자를 입력받을 때 해당 숫자가 해시에 없는 경우 값을 1으로 설정하고, 있는 경우 값에 1을 더한다.
숫자를 출력할 때 해당 숫자가 해시에 존재하면 해시의 값을 출력하고, 없는 경우 0을 출력한다.
 

💡코드

이분탐색 방법

import sys
input = sys.stdin.readline

N= int(input())
cards = list(map(int, input().split()))
M= int(input())
needs = list(map(int, input().split()))
cards.sort()

def upperBound(target):
    lo=0
    hi=len(cards)-1
    while lo<=hi:
        mid=(hi+lo)//2
        if cards[mid]>target:
            hi=mid-1
        else:
            lo=mid+1
    return lo

def lowerBound(target):
    lo=0
    hi=len(cards)-1
    while lo<=hi:
        mid=(hi+lo)//2
        if cards[mid]>=target:
            hi=mid-1
        else:
            lo=mid+1
    return lo

for i in needs:
    print(upperBound(i)-lowerBound(i), end=" ")

 
해시를 사용하는 방법

import sys
input = sys.stdin.readline

N= int(input())
cards = list(map(int, input().split()))
M= int(input())
needs = list(map(int, input().split()))
cards.sort()

count={}

for i in cards:
    if i in count:
        count[i]+=1
    else:
        count[i]=1
        
for i in needs:
    print(count[i] if i in count else 0, end=" ")

💡시간복잡도

이분 탐색 사용:
이분 탐색(O(logN))을 2번, 카드의 숫자(M)만큼
O(2*logN*M)
해시 사용: for문을 두번 돌리므로 O(N+M)

💡 틀린 이유

import sys
input = sys.stdin.readline

N= int(input())
cards = list(map(int, input().split()))
M= int(input())
needs = list(map(int, input().split()))
count=[0]*M
cards.sort()

for i in range(M):
    lo=0
    hi=len(cards)-1

    while lo<=hi:
        mid=(hi+lo)//2
        if cards[mid]==needs[i]:
            count[i]+=1
            cards.pop(mid)
            lo=0
            hi=len(cards)-1
        elif cards[mid]>needs[i]:
            hi=mid-1
        else:
            lo=mid+1

for i in range(M-1):
    print(count[i], end=" ")
print(count[M-1], end="")

 
탐색 후 카드를 발견하면 중복된 카드를 발견하기 위해 해당 카드를 리스트에서 삭제하고 다시 탐색을 시작하도록 했다.
어느 부분에서 틀렸습니다가 떴는지는 아직 잘 모르겠지만... 한번 탐색할 때 무조건 탐색이 두번씩 이루어지므로 비효율적이다. (왜 틀렸는지 아시는 분은 댓글로 도움 부탁드립니다. ^^)
 

💡 느낀점 or 기억할 정보

이분 탐색은 mid, hi, lo 설정이 헷갈리니 원리는 이해하되 구현은 외워서 하는게 편할 것 같다.
이분 탐색을 연습해보고 싶어 선택한 문제였으나, 해시를 사용하는게 더 편하고 빠르다. 잘 구분해서 사용하면 좋을 것 같다.