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

Silver Ⅳ 🔗14425. 문자열 집합

📝문제 요약

문제

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

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

입력

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

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

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

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

출력

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

✏️문제 풀이

• 입력
  • 문자열의 개수 n과 m을 공백을 기준으로 입력
  • n개의 줄에 걸쳐 들어오는 입력을 리스트 s에 저장
  • m개의 줄에 걸쳐 들어오는 입력을 리스트 check에 저장
• 집합 S에 포함되어 있는 문자열을 카운팅할 count 초기화
• check를 순회하여 해당 요소가 s에 포함된다면 count에 카운팅
• 집합 S에 포함되어 있는 문자열의 개수를 출력

생각해보기

• s가 list일 때
  • if i in s 연산이 O(n) 시간이 걸림
  • m개의 문자열을 각각 검색하므로 총 시간 복잡도는 O(nm)
  • 예를 들어 n=1000, m=1000이면 최악의 경우 1,000,000번의 비교가 필요
• s가 set일 때
  • if i in s 연산이 O(1) 시간이 걸림
  • m개의 문자열을 각각 검색하므로 총 시간 복잡도는 O(n + m)
  • 예를 들어 n=1000, m=1000이면 최악의 경우 2,000번의 연산만 필요

• 실제로 set으로 할 경우에는 시간이 584ms였으나 list일때는 4236ms가 걸렸다.

  

코드와 함께 보는 풀이

# 문자열의 개수 n과 m을 입력
n,m = map(int, input().split())
# n개의 줄에 걸쳐 들어오는 입력을 리스트 s에 저장
s = [input() for _ in range(n)]
# m개의 줄에 걸쳐 들어오는 입력을 리스트 check에 저장
check = [input() for _ in range(m)]

# 집합 S에 포함되어 있는 문자열을 카운팅할 count 초기화
count = 0

# check를 순회
for i in check:
		# 해당 요소가 s에 포함된다면 count에 카운팅
    if i in s:
        count += 1

# 집합 S에 포함되어 있는 문자열의 개수를 출력
print(count)

💯제출 코드

n,m = map(int, input().split())
s = [input() for _ in range(n)]
check = [input() for _ in range(m)]

count = 0

for i in check:
    if i in s:
        count += 1

print(count)