10816번 : 숫자 카드 2 - Python

문제

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

풀이

python의 딕셔너리를 사용하여 key값을 카드에 적힌 숫자, value를 개수로 하나씩 증가하면서 딕셔너리를 만들어준 다음에 출력해주면 된다.

또 다른 방법으로는 array를 이중배열로 만들어 array[i][0]에는 카드의 숫자, array[i][1]에는 카드의 개수를 저장한다음 이분 탐색으로 찾는 방법도 있다.

코드

from sys import stdin

input = stdin.readline

dic = dict()
n = int(input())

array = list(map(int,input().split()))
for i in array: #상근이가 가지고 있는 카드들을 딕셔너리에 넣는다.
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] +=1

m = int(input())
li = list(map(int,input().split()))

for i in li:
    if i in dic: #확인할 카드가 dic에 있다면 1을 출력한다.
        print(dic[i],end=' ')
    else:#없다면 0을 출력한다.
        print(0, end=' ')

코드(이분 탐색)

from sys import stdin

input = stdin.readline

#원하는 값(n)를 초과한 값이 처음 나오는 위치를 찾는 과정
def upperbound(array,n):
    start = 0
    end = len(array)-1

    while start<end:
        mid = (start+end)//2

        if n<array[mid]:
            end = mid
        else:
            start = mid+1
    if array[end]==n:
        return end+1
    return end

#원하는 값(n) 이상이 처음 나오는 위치를 찾는 과정
def lowerbound(array,n):
    start = 0
    end = len(array)-1

    while start<end:
        mid = (start+end)//2

        if n<=array[mid]:
            end = mid
        else:
            start = mid+1
    
    return end

        

n = int(input())
array = list(map(int,input().split()))
array.sort()#이분 탐색을 사용하기 위해서 값을 오름차순으로 정렬한다.
m = int(input())
li = list(map(int,input().split()))

for i in li:
    print(upperbound(array,i) - lowerbound(array,i),end=' ')

참고

JWonK