[BaekJoon] 1081 숫자 카드 2

[출처 : https://www.acmicpc.net/problem/10816]

 

● 입력으로 받은 두개의 리스트를 비교해 두번째 리스트에 있는 카드의 종류에따라 첫번째 배열에 있는 데이터가 몇개인지 계산하는 문제이다.

 

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
cardType = list(map(int, input().split()))

cards.sort()
cardDic = {key : 0 for key in cards}

for t in cards:
    cardDic[t] += 1

keyList = sorted(list(cardDic.keys()) )

def binarySearch (data, num):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2
        if data[mid] == num :
            return True

        elif num > data[mid] :
            low = mid + 1

        elif num < data[mid] : 
            high = mid - 1
    return False

for t in cardType:
    if binarySearch(keyList, t) == True:
        print(cardDic[t],end=' ')
    else: 
        print(0, end=' ')

풀이 과정은 다음과 같다.

 

1. 주어진 입력을 처리 => 이 과정에서 첫번째 배열의 카드 종류 각각의 수를 세어 cardDic에 저장

2. 효율성도 같이 고려해야 했기에 탐색과정에서 O(logN) 의 시간복잡도를 가지는 이진 탐색 메소드를 구현

3. 두번째 리스트의 원소를 하나씩 가져와 이진탐색을 통해 cardDic에 cardType이 저장되어 있는지를 판단

4. 만일 있다면 초기 cardDic에 저장했던 해당 카드 종류의 수를 출력해주고, 아니라면 0을 출력