[백준 10816] 숫자 카드 2

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

10816번: 숫자 카드 2

▶ 이분탐색으로 arr에 해당 숫자 있는지 구하고, 해당 숫자의 '개수' 구하는 문제 

▶ 이분탐색은 항상 arr이 정렬 되어있어야 한다.

 

---

▶ 시행착오 1

한번 찾은 값을 다시찾지 않기위해서, 10,000,001 과 같이 큰 숫자로 바꿔버리면, arr의 정렬된 형태가 깨져버린다. 

 

ex) [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10] 의 경우, '3'에 대한 이분탐색을 하면 두번째 위치한 3이 먼저 출력된다.

다음 3은 현재 index의 왼쪽에 있다.

ex) [-1, -1, -1, 3, 3] 의 경우 '3'에 대한 이분탐색을 하면 첫번째 위치한 3이 먼저 출력된다.

다음 3은 현재 index의 오른쪽에 있다.

 

▶ 시행착오 2

한번 찾은 값을 다시 찾지 않기 위해서, 따로 표시하는 방법은 어떨까.

그러나 이러한 과정을 거치면 시간초과

표시한다해도, 그다음 이분탐색으로 넘어갈때 같은 값이 왼쪽에 있는지 오른쪽에 있는지 모른다.

 

---

 

▶ 풀이방법 1 : 배열 count 함수 + 딕셔너리 사용   → 시간초과 (오답)

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

dic = {}
for c in card:
    dic[c] = lst.count(c)
print(' '.join(str(dic[c]) for c in card))

 

▶ 풀이방법 2: 이분 탐색 할때 해당 값 찾은후, 배열에서 count + 딕셔너리 사용 

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

def BinarySearch(lst, n, low, high):
    if low > high: # 이분탐색 조건 
        return -1

    mid = (low + high) // 2

    if n < lst[mid]:
        return BinarySearch(lst, n, low, mid-1)
    elif n > lst[mid]:
        return BinarySearch(lst, n, mid+1, high)
    else:
        return lst[low:high+1].count(n)

dic = {}
for n in lst:
    low = 0
    high = len(lst)-1
    if n not in dic:
        dic[n] = BinarySearch(lst, n, low, high)
        
#print(dic)

print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

            

 

▶ 풀이방법 3 : arr은 정렬되어있으므로, 이분 탐색으로 해당 값을 찾고, 양 옆에 같은 수 몇개 있는지 세기

+ 딕셔너리 사용

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

def BinarySearch(arr, val, low, high):
    if low > high:
        return 0

    mid = (low + high) // 2

    if val < arr[mid]:
        return BinarySearch(arr, val, low, mid-1)
    elif val > arr[mid]:
        return BinarySearch(arr, val, mid+1, high)
    else:
        i = 1
        j = 1
        c = 1
        while mid - i >= 0:
            if arr[mid] != arr[mid-i]:
                break
            else:
                c += 1
            i += 1
        while mid + j < len(arr):
            if arr[mid] != arr[mid+j]:
                break
            else:
                c += 1
            j += 1
        return c

dic = {}
for n in lst:
    if n not in dic:
        dic[n] = BinarySearch(lst, n, 0, len(lst)-1)
        
#print(dic)     
print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

 

→ 이분 탐색 함수에서 해당 값 찾고, while 문 안에서 같지 않은것 찾았을때 즉시 빠져나오는 break 해주지 않으면 시간초과 

 

 

▶ 풀이방법 4: 딕셔너리만 사용 

from collections import Counter

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))


dic = {}

for n in lst:
    if n in dic: # 딕셔너리에 있으면
        dic[n] += 1
    else: # 딕셔너리에 없으면
        dic[n] = 1

print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

 

▶ 풀이방법 5: collections 라이브러리의 Counter() 사용

from collections import Counter

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))


counter = Counter(lst)

print(' '.join(str(counter[c]) if c in counter else '0' for c in card))

 

출처 : (https://chancoding.tistory.com/45)