백준 10816 카드넘버2 문제풀이

📌문제설명

백준 10816 문제 설명

백준 10816 입출력 예시

📌문제접근방식

1차시도

3단계에 걸쳐 문제를 해결하려고 했다. 하지만 결과적으로 문제를 복잡하게 만들었다.

1. 입력받은 값을 정렬한다.

2. (입력받은 값, 개수)를 저장한 리스트를 생성한다.

3. 2번의 리스트에서 입력받은 값을 기준으로 이진탐색을 수행하고, 개수를 반환한다.

첫 시도는 이진 탐색을 사용했다.

이유는 숫자 카드 개수가 50만이었고, 숫자 카드의 범위가 -천만~+천만이었기 때문이다.

따라서 최악의 경우 50만 x 7log10을 계산하면 된다고 생각했다.

하지만 시간초과가 발생했다. 따라서 해쉬로 구현해야겠다는 생각이 들었다.

소스코드

import sys

n = int(sys.stdin.readline().rstrip())
cards = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(sys.stdin.readline().rstrip())
nums = list(map(int, sys.stdin.readline().rstrip().split()))
cards_set = list(set(cards))

cards.sort()
cards_set.sort()
cards_num = [cards_set[i] for i in range(len(cards_set))]
counts_num = [cards.count(cards_set[i]) for i in range(len(cards_set))]

def test(cards_num, num):
    left, right = 0, len(cards_num)
    while left <= right:
        mid = (left+right)//2
        if cards_num[mid] == num:
            return mid
        elif cards_num[mid] > num:
            right = mid-1
        else:
            left = mid+1
    return -1

def solution(cards_num, counts_num, nums):
    result = []
    for i in range(len(nums)):
        res = test(cards_num, nums[i])
        if res == -1:
            result.append(0)
        else:
            result.append(counts_num[res])
    return result

result = solution(cards_num, counts_num, nums)
for x in result:
    print(x, end=' ')

2차시도

두 번째는 딕셔너리를 이용했다.

리스트가 편하다보니 자꾸 리스트로 접근하게 되는 것 같다.

그래서 문제의 복잡도와 난이도가 올라갔다.

간단히 입력받은 수를 차례대로 딕셔너리의 key값으로 저장하고, value를 1씩 증가시키면 되는 문제였다.

 결과값으로는 해쉬에 해당 값이 있으면 value를 출력, 없으면 0을 출력하면 해결됬다.

소스코드

import sys

n = int(sys.stdin.readline().rstrip())
cards = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(sys.stdin.readline().rstrip())
nums = list(map(int, sys.stdin.readline().rstrip().split()))
cards_set = list(set(cards))
cards.sort()

def solution(cards_set, cards, nums):
    hashmap = {}
    for x in cards:
        if x in hashmap:
            hashmap[x] += 1
        else:
            hashmap[x] = 1
    return hashmap

hashmap = solution(cards_set, cards, nums)s
for x in nums:
    if x in hashmap:
        print(hashmap[x], end=' ')
    else:
        print('0', end=' ')