[알고리즘] 백준 10816 : 숫자 카드 2 - S4

2023.05.17 풀이

#0509 시간초과
import sys
input=sys.stdin.readline

n=int(input())
arr1=list(map(int, input().split()))
m=int(input())
arr2=list(map(int, input().split()))

arr1.sort()

def bs(left, right, k):
    if left>right:
        return 0
    mid=(left+right)//2
    if arr1[mid]==k:
        return arr1[left:right+1].count(k)
    elif arr1[mid]>k:
        return bs(left, mid-1, k)
    else:
        return bs(mid+1, right, k)

for i in arr2:
    print(bs(0, n-1, i), end=" ")

#2
import sys
input=sys.stdin.readline

n=int(input())
arr1=list(map(int, input().split()))
m=int(input())
arr2=list(map(int, input().split()))

arr1.sort()

res={}
for i in arr1:
    if i in res:
        res[i]+=1
    else:
        res[i]=1

def bs(left, right, k):
    if left>right:
        return 0
    mid=(left+right)//2
    if arr1[mid]==k:
        return res.get(k)
        # return arr1[left:right+1].count(k)
    elif arr1[mid]>k:
        return bs(left, mid-1, k)
    else:
        return bs(mid+1, right, k)

for i in arr2:
    print(bs(0, n-1, i), end=" ")

• 이분탐색까지는 파악하였으나 카운트하는 부분의 구현이 어려웠음
  첫 풀이는 최악의 경우(arr1[0]~arr1[n-1]까지 다 같은 경우) 탐색이 n번이기 때문에 풀면서 시간초과가 날 것 같았는데, 다른 풀이가 생각나지 않았고 타블로그 참고하였음

---

다른 풀이

1

from sys import stdin
_ = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
_ = stdin.readline()
M = map(int,stdin.readline().split())

def binary(n, N, start, end):
    if start > end:
        return 0
    m = (start+end)//2
    if n == N[m]:
        return N[start:end+1].count(n)
    elif n < N[m]:
        return binary(n, N, start, m-1)
    else:
        return binary(n, N, m+1, end)

n_dic = {}
for n in N:
    start = 0
    end = len(N) - 1
    if n not in n_dic:
        n_dic[n] = binary(n, N, start, end)

print(' '.join(str(n_dic[x]) if x in n_dic else '0' for x in M ))

2

from sys import stdin
_ = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
_ = stdin.readline()
M = list(map(int,stdin.readline().split()))
index, m_dic = 0, {}

for m in sorted(M):
    cnt = 0
    if m not in m_dic:
        while index < len(N):
            if m == N[index]:
                cnt += 1; index += 1
            elif m > N[index]:
                index += 1
            else: break
        m_dic[m] = cnt

print(' '.join(str(m_dic[m]) for m in M))

3

from sys import stdin
_ = stdin.readline()
N = map(int,stdin.readline().split())
_ = stdin.readline()
M = map(int,stdin.readline().split())
hashmap = {}
for n in N:
    if n in hashmap:
        hashmap[n] += 1
    else:
        hashmap[n] = 1

print(' '.join(str(hashmap[m]) if m in hashmap else '0' for m in M))

---

check point

• 주어지는 정수가 음수인 경우 리스트로 개수 카운트가 불가 -> ex. res[-2]+=1 은 -2를 의미하는게 아니기 때문
• 이럴땐 딕셔너리 키-벨류 이용하기!!!