[백준] 10816번 숫자 카드 2

사용 언어 - Python3

10816번: 숫자 카드 2 (실버4, 이분 탐색)

문제 ★이분 탐색 문제★

10816번: 숫자 카드 2

 

 

정답

시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !!

(코드 풀이)

1. 리스트 원소별 개수 구하기

mycard를 sorted 정렬하여 입력받는다. 정렬한 내카드를 한개씩 확인하면서 개수를 센다.

count = {} 딕셔너리를 만들어서 여러개일 경우 중복 개수를 세준다.

list_1 = [1, 1, 2]

count = {}
for c in list_1: #1.1 입력    #3.두번째 1 입력
	if c in count: #4.이미 count에 1이 들어가있다. 
    	count[c] += 1 #5.count[1]+=1
    else: 
    	count[c] = 1 #2. count[1]=1

 

2. 이분 탐색 함수정의

이분 탐색은 test 리스트 원소를 한개씩 검사해야하므로 target을 기준으로 한다. (for target in test)

시작값 > 끝값이라면, 0을 return

비교하려는 arr(mycard)와 target 값이 같다면, target 개수를 출력해야한다. 앞서 개수를 세둔 count 딕셔너리에서 target 개수를 get한다. count.get(target)

 

 

3. 재귀

비교하려는 arr(mycard)와 target 값이 작거나, 크면 start를 mid+1로, end를 mid-1로 범위를 줄여줘야한다.

이때 재귀함수를 사용해서 start, end 인자를 조정해준다.

# 정답1 - 이분탐색

import sys
input = sys.stdin.readline

n = int(input())
mycard = sorted(list(map(int,input().split())))
m = int(input())
test = list(map(int,input().split()))

count = {}
for c in mycard:
    if c in count:
        count[c] += 1
    else:
        count[c] = 1

def binarySearch(arr, target, start, end):
    if start > end:
        return 0
    
    mid = (start + end) // 2
    if arr[mid] == target:
        return count.get(target)
    elif arr[mid] < target:
        return binarySearch(arr, target, mid+1, end)
    else:
        return binarySearch(arr, target, start, mid-1)
    
for target in test:
    print(binarySearch(mycard, target, 0, n-1), end=" ")

 

 

sys로 input하고, 이분 탐색을 했는데도 count 함수를 사용했더니 시간 초과로 오답이 나왔다.

계산 함수는 되도록 사용하지 말아야 할 것 같다.

# 오답 - 시간초과
import sys
input = sys.stdin.readline()

n = int(input())
mycard = sorted(list(map(int,input().split())))
m = int(input())
card = list(map(int,input().split()))

ans = []

for c in card:
    start = 0
    end = n-1
    cnt = 0
    
    while start<= end:
        mid = (start+end)//2
        
        if mycard[mid] == c:
            cnt += mycard.count(c)
            break
        elif mycard[mid] < c:
            start =  mid+1
        else:
            end = mid-1

    ans.append(cnt)
    
print(*ans)

 

---

레퍼런스

• 딕셔너리를 이용하여 리스트 원소 개수 구하기

Python List 배열 요소 중복 횟수 구하는 방법 (count duplicates in list)

• 정답 참고

[백준 10816 파이썬] 숫자 카드 2 (실버4, 이분 탐색)

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부