[백준] 10815번 숫자 카드 - Python(1편)

문제 코드: https://www.acmicpc.net/problem/10815

 

이 문제의 주요 특징과 해결 방법을 분석해 보겠습니다. 모르는 개념이거나 이해가 잘 되지 않는 경우 해당 텍스트의 하이퍼링크를 클릭하면 관련 설명 글로 넘어가실 수 있습니다.

 

문제 개요

1. 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)
2. 확인해야 할 숫자의 개수 M  (1 ≤ M ≤ 500,000)
3. 각 숫자에 대해 상근이가 해당 카드를 가지고 있는지 확인

문제 분석

1. 대용량 데이터 처리: N과 M의 최댓값이 500,000으로, 단순 반복문으로는 시간 초과가 발생할 수 있습니다.
2. 이진 탐색 적용: 정렬된 배열에서 특정 값을 빠르게 찾을 수 있는 이진 탐색 알고리즘이 적합합니다.(3편)
   • 집합의 해시 테이블을 기반으로 코드를 구현할 수도 있습니다.(1편)
3. 입출력 최적화: 대량의 데이터를 처리해야 하므로, 빠른 입출력 방식을 사용해야 합니다.

해결 방법

1. 상근이의 숫자 카드를 입력받아 정렬합니다.
2. 확인할 숫자들에 대해 이진 탐색을 수행합니다.
   • 집합을 사용했을 경우 집합의 in 검색을 사용할 수 있습니다.
3. 결과에 따라 1(카드 있음) 또는 0(카드 없음)을 출력합니다.

---

 

일단 집합의 해시 테이블을 기반으로 코드를 구현해 보겠습니다. 아래는 전체 코드입니다.

import sys
input = sys.stdin.readline

N = int(input())
N_data = set(map(int, input().split()))
M = int(input())
M_data = list(map(int, input().split()))

stack = {}
for card in M_data:
    if card in N_data:
        stack[card] = 1
    else:
        stack[card] = 0

print(*stack.values())

 

코드를 분석해 보겠습니다.

1. 입력 처리

   import sys
   input = sys.stdin.readline
   
   N = int(input())	#O(1)
   N_data = set(map(int, input().split()))	#평균 O(N), 최악의 경우 O(N^2)
   M = int(input())	#O(1)
   M_data = list(map(int, input().split()))	#O(M)

   • sys.stdin.readline을 input으로 재정의하여 입력 속도를 개선합니다.
   • N과 M은 각각 가지고 있는 숫자 카드의 개수와 비교할 숫자 카드의 개수를 나타냅니다.
     • 사실 N과 M을 사용하지는 않습니다.
   • N_data는 가지고 있는 숫자 카드들을 집합으로 저장합니다.
   • M_data는 비교할 숫자 카드들을 리스트로 저장합니다.
2. 카드 비교 및 결과 저장

   stack = {}
   for card in M_data:	#O(M)
       if card in N_data:	#평균 O(1), 최악의 경우 O(N)
           stack[card] = 1	#평균 O(1)
       else:
           stack[card] = 0	#평균 O(1)

   • stack 딕셔너리를 생성하여 각 카드의 존재 여부를 저장합니다.
   • M_data의 각 카드에 대해 반복합니다.
   • 각 카드가 N_data 집합에 있으면 1, 없으면 0을 stack 딕셔너리에 저장합니다.
3. 결과 출력

   print(*stack.values())	#O(M)

   • stack 딕셔너리의 값들을 언패킹하여 출력합니다.

전체 시간 복잡도는 평균 O(N + M)이고, 최악의 경우 O(N^2 + M*N)입니다.

1. 집합 생성: 파이썬의 집합은 해시 테이블을 사용합니다. 평균적으로 O(N) 시간이 걸리지만, 최악의 경우(많은 해시 충돌 발생 시) O(N^2)까지 갈 수 있습니다.
2. 집합 검색: card in N_data는 평균적으로 O(1)이지만, 최악의 경우 O(N)까지 갈 수 있습니다. 이는 해시 충돌이 많이 발생할 때 나타납니다.
3. 딕셔너리 연산: ' stack[card] = ...'은 평균적으로 O(1) 시간이 걸립니다.

 

2편에서는 이 코드를 압축하고 최적화한 버전을 확인해보겠습니다.

 

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.