2022.02.24 [백준] (python 파이썬) 숫자 카드 2

 

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

10816번: 숫자 카드 2

 

---

풀이

이 문제를 처음 접근할 때, 이분탐색으로 접근해서 코드를 작성했다.

하지만 계속 시간초과가 발생하여서 구글링으로 다른 방법을 찾아보았다.

1. 딕셔너리 활용하기

2. from collections import Counter를 이용해 개수 카운팅하기.

 

- 이분탐색( 시간초과 코드 )

n=int(input())
card=list(map(int,input().split()))
card.sort()
m=int(input())
nums=list(map(int,input().split()))
 
def binary_search(arr,value,a):
    global cnt
    start=0
    end=len(arr)-1
    while start<=end:
        mid = (end+start) // 2
        if arr[mid] == value:
            return card[start:end+1].count(value)
        elif arr[mid]<value:
            start=mid+1
        else:
            end=mid-1
    return 0
 
for i in range(len(nums)):
    print(binary_search(card,nums[i],i),end=' ')
 
 
 

 

 

1. 딕셔너리를 이용한 코드

 

우선 딕셔너리를 선언해준 뒤, 반복문을 이용해 nums에 있는 데이터값을 딕셔너리배열에 추가해준다.

다시 반복문을 이용해 card안에 있는 데이터가 dict에 있으면 value를 증가 시켜준다.

n=int(input())
card=list(map(int,input().split()))
m=int(input())
nums=list(map(int,input().split()))
 
dict={}
for i in nums:
    dict[i]=0
 
for i in card:
    if i in dict.keys():
        dict[i]+=1
 
for i in nums:
    print(dict[i],end=' ')

 

 

2. Counter함수를 이용한 코드

 

예시)
10
6 3 2 10 10 10 -10 -10 7 3
8
10 10 -5 2 3 4 5 -10

Counter({10: 3, -10: 2, 3: 2, 2: 1, 6: 1, 7: 1})

Counter를 배열에 사용하면 위의 예시와 같이 해당 값이 배열에 몇개가 있는지 딕셔너리 형식으로 보여준다.

그리고 for문을 이용하여 nums의 인덱스값이 count의 키값으로 있으면 키의  value를 출력하고 없으면 0을 출력하게 했다.

from collections import Counter
n=int(input())
card=list(map(int,input().split()))
card.sort()
m=int(input())
nums=list(map(int,input().split()))
count = Counter(card)
 
print(' '.join(str(count[i]) if i in count else '0' for i in nums))