[백준 / python] 10816번 숫자 카드 2

오늘은 이분 탐색 유형인 백준 10816번 문제, 숫자 카드 2를 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기 

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

숫자 카드 2 문제는 총 2가지 방법으로 풀어보겠습니다!

<<<  1. 이분 탐색  2. 해시맵  >>>

 

1️⃣ 이분 탐색(binary search)

검색 범위를 줄여나가며 특정 데이터를 검색하는 방식으로, 정렬된 정수의 리스트를 같은 크기의

두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다.

 

리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지

판단하여 맨 앞부터 검색하거나 중간부터 검색하여 범위를 줄여나가는 것입니다.

 

이번에는 python 내장 함수를 사용하여 보다 편리하게 코드를 작성해보겠습니다!

Thank you bisect !!

 

✔️ 가능한 시간복잡도 (1)

N개의 정수 배열을 정렬하는 데 O(NlogN), M개의 숫자 각각 이분 탐색을 적용하는데

총 O(MlogN)의 시간이 소요되므로, 전체 시간복잡도는 O(NlogN+MlogN)입니다.

---

2️⃣ 해시맵(딕셔너리)

숫자 카드가 몇 개 있는지 세어야 하는 문제로 효율적으로 해결하기 위해 이진 탐색을 사용할 수 있지만,

해시맵을 이용한 접근이 더 빠릅니다! 따라서, 이번 문제는 해시맵을 이용하여 풀어보도록 하겠습니다!

 

해시맵과 관련된 상세한 내용은 아래 블로그를 참고하여 확인하였습니다 :)

[파이썬으로 배우는 자료구조] 해시(Hash)

상근이가 가진 카드의 개수를 효율적으로 세기 위해 해시맵(딕셔너리)을 사용하고

각 숫자가 상근이가 가진 카드에 몇 번 나타나는지를 확인하고 출력합니다.

 

딕셔너리에 저장할 때 키는 카드의 수, 값은 카드의 개수입니다.

 

여기서! 딕셔너리를 생성할 때 defaultdict를 사용합니다!

011 딕셔너리를 한 번에 초기화하려면? ― collections.defaultdict

defaultdict(int)을 사용해 숫자 카드 리스트 numbers에서 각 숫자의 개수를 세고,

M_list에 있는 각 숫자에 대해 해시맵에서 개수를 조회하여 results 리스트에 저장하여

최종적으로 결과를 출력해야 할 것입니다!

 

✔️ 가능한 시간복잡도 (2)

카드의 개수를 세는데 O(N), 과정을 처리하는데 O(M)

총 O(N + M)으로 이분 탐색보다 훨씬 빠른 시간에 계산이 가능합니다!

 

✔️ 추가 꿀팁!

코딩테스트와 관련된 여러 블로그를 찾아보다가 python을 활용해서 리스트의 내용을

공백을 기준으로 한 줄에 출력할 수 있는 아주 쉬운 코드를 발견했다!

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

# 실행 결과
1 2 3 4 5

이렇게 리스트 변수명 앞에 *만 붙여주면 모든 원소를 출력할 수 있다!

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. sys.stdin.read를 사용하여 입력 데이터를 한 번에 읽어오고, split()을 사용해 공백 단위로 나눕니다.

2. 상근이가 가지고 있는 카드의 수 N을 입력받고, N개의 숫자를 numbers 리스트로 만듭니다.

3. 이어서 찾고자 하는 숫자 리스트의 크기 M을 입력받고, 각 숫자를 M_list로 만듭니다.

4.해시맵을 이용하여 카드 개수를 카운팅하여 result에 저장 후 출력합니다.

 

---

📌 시도 회차 수정 사항 (Optional)

무문 별하게 “맞았습니다”가 나올 때까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

1. 입력 데이터의 정확성 확인

입력 데이터가 제대로 들어왔는지, 특히 N과 M이 기대한 대로 들어왔는지 확인해야 합니다.

sys.stdin.read를 사용하여 데이터를 가져올 때, 추가 공백이나 예상치 못한 데이터가 섞일 수 있습니다.

 

2. 인덱스 계산 오류 방지

처음에 data[N+2:] 이렇게 작성하니 런타임 에러가 발생했습니다.🙄🙄🙄

data[N+2:]는 리스트에서 N+2 인덱스부터 끝까지 슬라이싱하는데 N이 제대로 정의되지 않았거나,

N의 값이 실제 리스트의 길이보다 커서, N+2가 data 리스트의 범위를 벗어난 경우

data[N+2:]가 빈 리스트가 되거나, 아예 슬라이싱이 불가능한 상황이 발생할 수 있다고 합니다...

 

 

---

📌 정답 코드

1. 이분 탐색 알고리즘 활용

import sys, bisect

input = sys.stdin.read

# 입력 받기
N = int(input().strip())
numbers = list(map(int, input().strip().split()))
numbers.sort()  # 숫자 카드 정렬

M = int(input().strip())
M_list = list(map(int, input().strip().split()))

# 이분 탐색 알고리즘 (내장함수 사용)
def num_count(arr, value):
    left_index = bisect.bisect_left(arr, value)
    right_index = bisect.bisect_right(arr, value)
    return right_index - left_index

result = []
for i in M_list:
    result.append(str(num_count(numbers, i)))

print(*result)

 

2. 해시맵

import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
numbers = list(map(int, data[1:N+1]))
M = int(data[N+1])
M_list = list(map(int, data[N+2:N+2+M]))

# 카드 개수를 저장할 딕셔너리
num_count = defaultdict(int)

# 카드 개수 세기
for card in numbers:
    num_count[card] += 1

results = []
for i in M_list:
    results.append(num_count[i])

print(*results)

 

오늘은 이분 탐색 알고리즘과 해시맵을 동시에 사용하여 문제를 풀어보았습니다.

시간은 해시맵이 빨랐지만 메모리 사용은 더 많음을 확인했습니다.

문제에 따라 다를 수 있지만 여러가지 방법을 시도해보면서 문제풀이 능력을 기르고 싶습니다!!

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no