[백준/Python] 14425 문자열 집합

[백준/Python] 14425 문자열 집합

풀이 코드 및 설명

import sys

N, M = map(int, sys.stdin.readline().split())
S = set(sys.stdin.readline().strip() for _ in range(N))

count = 0 

for _ in range(M):
    query = sys.stdin.readline().strip()
    if query in S:
        count += 1 

print(count)

문자열 탐색 문제를 해결하기 위해 문자열 탐색에 쓸 수 있는 방법을 찾아보았다. 문자열 탐색에 사용할 수 있는 건 해쉬 테이블, 파이썬에서 집합 자료형 SET이나 Dict 을 사용하는 것이다.

위 코드는 set 을 이용하여 풀어보았다.

아래는 dict 을 사용하여 풀어본 코드이다.

import sys

N, M = map(int, sys.stdin.readline().split())
S = {sys.stdin.readline().strip(): True for _ in range(N)} 
count = 0
for _ in range(M):
    query = sys.stdin.readline().strip()
    if query in S:  
        count += 1

print(count)

Python 해시 테이블 기반 딕셔너리(dict) 과 set

dict, 딕셔너리

• 정의 : 'dict'은 키 - 값 쌍으로 데이터를 저장한다. 각 키는 유일해야 하며, 각 키에는 하나의 값이 할당된다
• 용도 : 데이터에 빠르게 접근해야 할 때 유용하다. 특히 데이터에 고유한 식별자(키) 가 있고 이를 통해 데이터(값) 에 접근해야 할 때 적합하다.
• 특징
  1. 키는 변경 불가능한 타입이여야 한다.
  2. 값은 어떤 데이터 타입이든 될 수 있다.
  3. 딕셔너리는 중괄호 {} 또는 dict() 생성자로
  4. 순서가 없다.
• 예시

my_dict = {'apple': 5, 'banana': 3, 'orange': 2}
print(my_dict['apple'])  # 5 출력
my_dict['banana'] = 4
print(my_dict)  # {'apple': 5, 'banana': 4, 'orange': 2}

set

• 정의 : 유일한 요소들의 집합이다. 중복된 요소는 저장되지 않는다.
• 사용 용도 : set 은 주로 데이터의 중복을 제거하거나, 데이터 존재의 여부만을 빠르게 확인할 때 사용
• 특징
  1. 중복된 요소 저장하지 않음
  2. 순서가 없음
  3. 변경 가능한 데이터 타입이다
  4. 중괄호 {} 또는 set() 생성자로 만든다.
  5. 요소는 변경 불가능한 타입이어야한다.
• 예시

my_set = {1, 2, 3, 2, 3}
print(my_set)  # {1, 2, 3} 출력
my_set.add(4)
print(my_set)  # {1, 2, 3, 4}

set 과 dict 비교

• 공통점 : 둘 다 해시 테이블을 사용해서 데이터를 저장한다. 때문에 데이터 조회 및 추가의 시간 복잡도가 평균적으로 O(1) 이다.
• 차이점 : dict 은 키-값 쌍으로 데이터를 저장하는 반면, 'set' 은 유일한 값만을 저장한다.