[백준] 10816. 숫자 카드 2

백준 10816. 숫자카드 2

10816번: 숫자 카드 2

 

✓ 실버 4

 

 

✓ 문제풀이 : 카운터 함수

from collections import Counter
import sys
input = sys.stdin.readline


n = int(input())
num = list(map(int, input().split()))
m = int(input())
chk = list(map(int, input().split()))
res = []

count = Counter(num)
num = set(num)

for c in chk:
    if c in num:
        res.append(count[c])
    else:
        res.append(0)

print(' '.join(map(str, res)))

 

---

< 풀이 : 이분탐색 (시간초과) >

import sys
input = sys.stdin.readline

n = int(input())
num = list(map(int, input().split()))   #숫자 카드의 수
m = int(input())
chk = list(map(int, input().split()))   #확인할 수
res = []    #답

num.sort()

for c in chk:
    s, e = 0, n-1
    cnt = 0
    while s <= e:
        mid = (s+e)//2
        
        #카드에 수가 존재하는 경우
        if num[mid] == c:
            cnt += 1
            
            #앞-뒤로 같은 수가 있는 경우 체크
            #앞의 수 체크
            for i in range(mid-1, -1, -1):
                if num[i] == c:
                    cnt += 1
                else:
                    break
                
            #뒤의 수 체크
            for j in range(mid+1, n):
                if num[j] == c:
                    cnt += 1
                else:
                    break
            
            #이분탐색 종료 (같은 수의 값 다 찾음)
            break
        
        # 주어진 수보다 작은 경우
        elif num[mid] < c:
            s = mid+1
        
        # 주어진 수보다 큰 경우
        else:
            e = mid-1
            
    
    res.append(str(cnt))

print(' '.join(res))

 

< 풀이 : 배열 >

from collections import Counter
import sys
input = sys.stdin.readline


n = int(input())
num = list(map(int, input().split()))
m = int(input())
chk = list(map(int, input().split()))
res = [0] * 20000001

for i in num:
    res[i+10000000] += 1

for j in chk:
    print(res[j+10000000], end=' ')

 

먼저 문제 아이디어로 이분탐색, 카운트 함수, 배열 이렇게 3가지 방법을 떠올렸다.

지금은 이분탐색을 공부하는 중이여서 이분 탐색으로 먼저 풀었다.

이분탐색으로 접근을 했을 때 찾은 수 앞 뒤로 카운팅을 해줬더니 시간초과가 났다..

일단 다른 방법도 되나 하고 카운트를 했을때 카운트는 성공했지만, 이분탐색은 아직도 잘 모르겠다.

다른 분들 풀이를 참고하니 딕셔너리에 존재하는지 여부를 이분탐색으로 푸셨던데 굳이..? 알고리즘이 효율적인지는 잘 모르겠다..

(아니라면 이유 좀 알려주세요.. 😂)

이거보다 bisect 함수를 공부해보는게 더 좋을 것 같다.

그리고 count 안에서 존재하는지 여부를 확인할 때, 리스트는 시간초과가 발생하고 set과 dict는 발생하지 않는다.

list보다 set, dict에서 시간복잡도가 확실히 낮다는 것을 알 수 있었다.