[백준][Python] 10816. 숫자 카드 2

Silver Ⅳ 🔗10816. 숫자 카드 2

📝문제 요약

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

✏️문제 풀이- 입력

- 가지고 있는 카드의 개수 `n` 입력
- 가지고 있는 카드의 숫자 입력을 리스트 `card`에 저장
- 찾아야 할 숫자의 개수 `m` 입력
- 찾아야 할 숫자 입력을 리스트 `solved`에 저장 - `sort()` 메서드를 사용하여 이진 탐색을 위해 리스트 `card`를 정렬 - 이진 탐색으로 target의 시작 위치를 찾는 함수 `lower_bound()` 정의
- 시작점(배열의 첫번째 인덱스) `left`와 끝점(배열의 마지막 인덱스) `right`초기화
- `left`가 `right` 보다 작아질 때까지 반복
    - 중간값은 시작점과 끝점을 더한 값에서 반인 지점
    - 중간값이 `target`보다 크거나 같으면 왼쪽 범위 탐색
    - 중간값이 `target`보다 작으면 오른쪽 범위 탐색
- `left` 반환 - 이진 탐색으로 target의 끝 위치를 찾는 함수 `upper_bound()` 정의(`lower_bound()`와 동일) - 각 숫자의 개수를 계산하여 출력
- `upper_bound`와 `lower_bound`의 차이로 해당 숫자의 개수를 구함

코드와 함께 보는 풀이

# 가지고 있는 카드의 개수 n 입력
n = int(input())
# 가지고 있는 카드의 숫자 입력을 리스트 card에 저장
card = list(map(int, input().split()))
# 찾아야 할 숫자의 개수 m 입력
m = int(input())
# 찾아야 할 숫자 입력을 리스트 solved에 저장
solved = list(map(int, input().split()))

# 이진 탐색을 위해 리스트 card를 정렬
card.sort()

# 이진 탐색으로 target의 시작 위치를 찾는 함수
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        # 중간값이 target보다 크거나 같으면 왼쪽 범위 탐색
        if arr[mid] >= target:
            right = mid
        # 중간값이 target보다 작으면 오른쪽 범위 탐색
        else:
            left = mid + 1
    return left

# 이진 탐색으로 target의 끝 위치를 찾는 함수
def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        # 중간값이 target보다 크면 왼쪽 범위 탐색
        if arr[mid] > target:
            right = mid
        # 중간값이 target보다 작거나 같으면 오른쪽 범위 탐색
        else:
            left = mid + 1
    return left

# 각 숫자의 개수를 계산하여 출력
for i in solved:
		# upper_bound와 lower_bound의 차이로 해당 숫자의 개수를 구함
    print(upper_bound(card, i) - lower_bound(card, i), end=' ')

💯제출 코드

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

card.sort()

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > target:
            right = mid
        else:
            left = mid + 1
    return left

for i in solved:
    print(upper_bound(card, i) - lower_bound(card, i), end=' ')