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=" ")

💡시간복잡도

이분 탐색 사용: