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

14425번: 문자열 집합

시간 제한	메모리 제한	문제 티어	정답 비율
2 초	1536 MB	실버 III	53.642%

📜 문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

 

📥입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

 

 

📤출력

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

 

💡풀이

이 문제는 List로 풀 수 있으나, 역시 시간 초과 문제가 발생한다. 따라서 우리는 리스트 대신 시간복잡도가 비교적 낮은 Set나 Dictionary를 사용해야 한다.

 

참고로 정리하자면 파이썬의 리스트(List), 집합(Set), 딕셔너리(Dictionary)는 각각 다른 데이터 구조를 나타낸다. 이들 각각의 시간 복잡도 차이는 내부적으로 사용되는 데이터 구조와 연산 방식에 기인한다. 리스트는 원소의 추가와 삭제에 있어서 선형 시간 O(n)이 소요되는 반면, 집합과 딕셔너리는 해시 함수를 이용하여 원소를 저장하고 조회하기 때문에 상수 시간 O(1) 내에 이루어질 수 있다.

 

Set와 Dictionary로 풀이한 코드는 아래와 같다.

1) Set를 이용한 풀이

import sys

input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

S = set()
count = 0

for _ in range(N):
  S.add(input().rstrip())

for _ in range(M):
  if input().rstrip() in S:
    count += 1

print(count)

 

2) Dictionary로 이용한 풀이

import sys

input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

S = {}
count = 0

for _ in range(N):
  S[input().rstrip()] = 0

for _ in range(M):
  if input().rstrip() in S:
    count += 1

print(count)​

 

 

<List, Set, Dictionary의 특징과 시간복잡도 정리>

리스트(List) : 순서가 있는 데이터의 모음.
● 리스트의 원소는 인덱스로 접근할 수 있으며, 원소의 추가, 삭제, 수정 등의 작업이 가능하다.
● 인덱스를 이용하여 원소를 조회하거나 수정하는 연산은 O(1)의 시간 복잡도를 가지지만, 원소를 추가하거나 삭제하는 경우에는 해당 위치에 따라 다르며, 평균적으로는 O(n)의 시간 복잡도를 가진다. 이는 리스트의 크기에 비례하는 선형 시간 복잡도이다.

집합(Set) : 순서가 없는 고유한 값을 가지는 데이터의 모음.
● 집합은 중복된 값을 허용하지 않으며, 원소의 추가, 삭제, 조회 등의 작업이 가능하다.
● 집합의 원소를 추가하거나 삭제하는 연산은 평균적으로 O(1)의 시간 복잡도를 가지는데 이는 해시 함수를 이용하여 원소를 저장하기 때문이다.

딕셔너리(Dictionary) : 키(key)와 값(value)의 쌍으로 이루어진 데이터의 모음.
● 딕셔너리는 키를 기반으로 값을 조회하고, 키를 추가하거나 삭제하는 작업이 가능하다.
● 딕셔너리는 해시 테이블을 사용하여 데이터를 저장하며, 키를 기반으로 값을 조회하는 연산은 평균적으로 O(1)의 시간 복잡도를 가진다.
● 하지만 키를 추가하거나 삭제하는 경우에는 해시 충돌이 발생할 수 있으며, 이 경우에는 선형 탐사 등의 추가 작업이 필요하여 최악의 경우에는 O(n)의 시간 복잡도를 가질 수도 있다.