[백준/파이썬] 18119번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 18119번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다.
다음과 같은 쿼리들이 주어진다.
-
1 x : 알파벳 x를 잊는다.
-
2 x : 알파벳 x를 기억해 낸다.
처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다.
각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.
입력 요약
첫 번째 줄에는 정수 N (1 ≤ N ≤ 104)과 M (1 ≤ M ≤ 5×104)이 주어진다.
다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 103을 넘지 않는다.
다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x는 알파벳 소문자이다.
o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.
출력 요약
각 쿼리마다 정수 하나를 출력한다.
코드
import sys; read = sys.stdin.readline
def strToBit(word):
result = 0
for ch in word: result |= 1 << (ord(ch) - ord('a'))
return result
n, m = map(int, read().split())
words = [strToBit(read()[:-1]) for _ in range(n)]
memory = strToBit(map(lambda i: chr(ord('a')+i), range(26)))
result = []
for i in range(m):
query, ch = input().split()
query = int(query)
if query == 2: memory |= strToBit(ch)
else: memory &= ~strToBit(ch)
cnt = 0
for word in words:
if word & memory == word: cnt += 1
result.append(str(cnt))
print('\n'.join(result))
설명
핵심은 구현 관점에서 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다.
다음과 같은 쿼리들이 주어진다.
- 1 x : 알파벳 x를 잊는다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기