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

N개의 숫자 카드를 가지고 있고, 정수 M개가 주어졌을 때, 이 수가 적힌 숫자 카드룰 몇개 가지고 있는지 구하는 문제이다.

이렇게 적혀 있었지만 그냥 코드를 짜보았다.

from collections import deque
import sys

input = sys.stdin.readline

N = int(input())
kards = list(map(int, input().split()))
M = int(input())
targets = list(map(int, input().split()))

for n in targets:
    print(kards.count(n), end = " ")

음! 역시나 시간 초과가 뜬다. 이분 탐색을 이용해보도록 하자.

import sys
input = sys.stdin.readline

N = int(input())
kards = list(map(int, input().split()))
kards.sort()
M = int(input())
targets = list(map(int, input().split()))

#카드별 개수 카운팅
count = {}
for n in kards:
    if n in count:
        count[n] += 1
    else:
        count[n] = 1

#이진 탐색 함수 
def BinarySearch(target, arr, start, end):
    while start <= end:
        mid = (start + end) // 2

        if target == arr[mid]:
            return count[target]        
        elif target > arr[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return 0

for n in targets:
    print(BinarySearch(n, kards, 0, len(kards) - 1), end = " ")

그래도 엄청 걸린다...

파이썬에서 함수구현부 이전에 쓰인 변수들은 전역변수이다.
파이썬은 함수 밖(전역 영역)에서 입력, 출력, 계산, 실행 모두 가능하다.
C언어에서는 전역 영역에서 정의/선언만 가능하다. 실행은 모두 main에서.
즉 파이썬은 위에서 하나하나 실행시키기 때문에 전역에서 뭘 하든 상관이 없음.
C는 전역 영역에 있는 것들을 미리 메모리영역에 할당만 한다. (미리 메모리 구조를 다 짜놓음)

연산 하느라 시간이 걸리는 것 같으니까 숫자 탐색을 없애고 딕셔너리의 get을 쓴다면?

import sys
input = sys.stdin.readline

N = int(input())
kards = list(map(int, input().split()))
kards.sort()
M = int(input())
targets = list(map(int, input().split()))

count = {}
for n in kards:
    if n in count:
        count[n] += 1
    else:
        count[n] = 1

for n in targets:
    print(count.get(n, 0), end = " ")