숫자 카드 1

https://www.acmicpc.net/problem/10815

입력 예시

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

출력 예시

1 0 0 1 1 0 0 1

제출 코드

# https://www.acmicpc.net/problem/10815
# 숫자 카드

N = int(input())
num_cards = list(map(int, input().split()))
M = int(input())
num_arr = list(map(int, input().split()))
num_cards.sort()
answer = []

def binary_search(num_cards, val):
    left, right = 0, len(num_cards) - 1
    while left <= right:
        mid = (left + right) // 2
        if num_cards[mid] == val:
            return True
        elif num_cards[mid] > val:
            right = mid - 1
        else:
            left = mid + 1
    return False

for num in num_arr:
    if binary_search(num_cards, num):
        answer.append(1)
    else:
        answer.append(0)

print(*answer)

이진탐색은 정렬된 리스트에만 적용할 수 있다.

• 입력 값의 범위: N(1 ≤ N ≤ 500,000), M(1 ≤ M ≤ 500,000)

입력 값의 범위가 선형탐색으로는 시간초과가 날 것 같아 이진 탐색을 선택했다. + 문제 분류에 이진탐색이라고 스포 당함
선형 탐색의 경우 빅오는 O(N*M)으로 최대 2500억번 연산이 진행되는 반면,
이진탐색을 사용할 경우 시간 복잡도는 O(N log M)으로 상당히 효율적이다.

이진탐색 메서드 binary_search()를 통해 num_cards의 숫자가 num_arr에 있는지 확인하고
있으면 answer에 1을 append, 없으면 0을 append 한다.

---

숫자 카드 2

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

입력 예시

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

출력 예시

3 0 0 1 2 0 0 2

제출 코드

N = int(input())
num_cards = list(map(int, input().split())) # 상근이가 가지고 있는 숫자 카드
M = int(input())
num_arr = list(map(int, input().split()))   # 몇 개 가지고 있는 숫자 카드인지 구해야 할 목록

answer = []

num_dict = {}
for num in num_arr:
    num_dict[num] = 0

for num in num_cards:
    if num in num_dict.keys():
        num_dict[num] += 1
    else:
        continue

for n in num_arr:
    if n in num_dict:
        answer.append(num_dict[n])
    else:
        answer.append(0)

print(*answer)

숫자 카드 목록에서 숫자들을 key로, 숫자들의 빈도를 value로 하는 num_dict 딕셔너리를 만들었다.
num_cards 리스트를 순회하며 숫자가 num_dict에 존재하면 1을 증가시킨다.
마지막으로 숫자가 num_dict의 key 값으로 존재하면 answer에 value를 append하고 없으면 0을 append한다.

---

회고

오늘 배운 것

• 파이썬 *는 Unpacking 역할을 한다. 리스트나 튜플, 딕셔너리 안의 데이터들을 풀어 각각의 값으로 만들어 준다.

list_data = [1,2,3,4,5]
print(list_data)
[1, 2, 3, 4, 5]

print(*list_data)
1 2 3 4 5

tuple_data = (1,2,3,4,5)
print(tuple_data)
(1, 2, 3, 4, 5)

print(*tuple_data)
1 2 3 4 5

• dictionary는 key 값들로 풀어진다.

dict_data = {1: "ab", 2: "cd", 3: "ef", 4: "gh"}

print(dict_data)
{1: 'ab', 2: 'cd', 3: 'ef', 4: 'gh'}

print(*dict_data)
1 2 3 4