[파이썬/Python] 백준 10816번: 숫자 카드 2

숨·2024년 7월 7일

알고리즘 문제 풀이

목록 보기

17/128

📌 문제 : 백준 10816번

📌 문제 탐색하기

N : 숫자 카드의 수 (1 ≤ N ≤ 500,000)
M : 가지고 있는 수를 구해야 할 정수의 수 (1 ≤ M ≤ 500,000)
n, m : 각 카드에 적힌 수 (-10,000,000 ≤ n, m ≤ 10,000,000)

✅ 입력 조건
1. N 입력
2. N개의 정수를 공백으로 구분해 입력
3. M 입력
4. M개의 정수를 공백으로 구분해 입력
✅ 출력 조건
1. M개의 정수가 N개의 정수 중에 있는지 몇 개 있는지 공백 구분해 출력

처음엔 지난번 수 찾기 문제처럼 이분 탐색을 구현하려고 했다.
하지만 정수의 크기가 매우 큰 경우, for문이나 while문이 여러 개 들어간다면 시간 초과가 발생한다.

따라서, 각 원소의 개수를 셀 수 있는 collections 모듈의 Counter 클래스를 사용하려고 한다.

입력받은 N개의 정수와 M개의 정수를 리스트에 저장하고, N개의 정수가 저장된 리스트를 Counter 객체로 만들어주어 개수를 센다.

for문으로 M개의 정수를 저장한 리스트를 돌면서 저장된 개수가 있으면 개수를 출력하고, 없으면 0을 출력하는 식으로 작성했다.

가능한 시간복잡도

입력받아 리스트 만들기 → $O(N)$ , $O(M)$
Counter 모듈로 수 세기 → $O(N)$
for 루프로 출력하기 → $O(M)$

최종 시간복잡도
$O(N + M)$ 으로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

Counter 모듈을 활용해 수를 세고 출력하기.

📌 코드 설계하기

N 입력
N개의 정수 입력받아 n에 저장
M 입력
M개의 정수 입력받아 target에 저장
Counter 모듈로 개수 세기
for문으로 알고 싶은 정수의 개수 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys
from collections import Counter

input = sys.stdin.readline

# 1. N 입력
N = int(input())

# 2. N개의 정수 입력받아 n에 저장
n = list(map(int, input().split()))

# 3. M 입력
M = int(input())

# 4. M개의 정수 입력받아 target에 저장
target = list(map(int, input().split()))

# 5. Counter 모듈로 개수 세기
count = Counter(n)

# 6. for문으로 알고 싶은 정수의 개수 출력
for i in range(M):
    if target[i] in count:
        print(count[target[i]], end=' ')
    else:
        print(0, end=' ')

결과

다른 풀이 1

import sys

input = sys.stdin.readline

# 1. N 입력
N = input().rstrip()

# 2. N개 정수 리스트에 저장
A = list(map(int, input().split()))

# 3. M 입력
M = input().rstrip()

# 4. M개 정수 리스트에 저장
target_list = list(map(int, input().split()))

# 5. 해시 맵 생성
hash = {}

for i in A:
    if i in hash:
        hash[i] += 1
    else:
        hash[i] = 1
        
# 6. 빈도수 출력
for i in target_list:
    if i in hash:
        print(hash[i], end=' ')
    else:
        print(0, end=' ')

결과
Counter를 이용해 푼 문제와 동일한 시간복잡도를 가졌지만 시간이 가장 적게 걸렸다.
정답 코드와는 달리 정수 변환 과정도 빠지고, 해시맵을 직접 생성해 활용하는 부분에서 시간 차이가 생긴 것 같다.

다른 풀이 2

import sys

input = sys.stdin.readline

# 1. N 입력
N = input().rstrip()

# 2. N개의 정수 입력받아 리스트에 저장
A = list(map(int, input().split()))

# 3. M 입력
M = input().rstrip()

# 4. M개의 정수 입력받아 리스트에 저장
target_list = list(map(int, input().split()))

# 5. 해시맵 만들기
hash = {}

# 6. 개수 세기
for i in A:
    hash[i] = hash.get(i, 0) + 1

# 7. 개수 출력
for i in target_list:
    print(hash.get(i, 0), end=' ')

결과
.get()메소드를 사용했더니 코드를 좀 더 간결하게 작성할 수 있었다.

📌 회고

코딩테스트에서 이용하면 좋을 라이브러리, 모듈들을 따로 정리해서 사용법을 익혀두는 것이 좋을 것 같다.
스택이나 큐는 다뤄봤지만 해시맵은 아직 익숙하지 않은 것 같다.

📌 기억할 정보

📖 collections의 Counter
from collections import Counter
여러 형태의 데이터(0 또는 음수 값도 가능)를 인자로 받는다.

중복된 데이터가 있는 배열을 인자로 넘기면 각 원소와 그 개수가 저장된 객체를 얻을 수 있다.

각 값들은 딕셔너리 형태로 저장

key : element

value : element 개수

누락 항목에 대해서 KeyError 발생 ❌ → 0 반환

생성 시 시간 복잡도 : $O(n)$

Method

n개의 상위 요소 반환 → most_common(n)

전체 개수(value의 합) 계산해 반환 → total()

카운터 숫자만큼 요소 반환 → elements()

각 요소의 값 빼기 → subtract()

요소 완전 제거 → del

두 카운터 더하기 & 빼기 → +, -

교집합 / 합집합 연산 → &, |