문제 링크
문제 요약
‘좋은 단어’는 주어진 단어의 모든 문자를 같은 문자끼리(A는 A끼리, B는 B끼리) 짝지었을 때, 짝지은 선들이 교차하지 않으면서 모든 문자가 정확히 하나의 짝을 가지는 단어를 의미합니다. 주어진 N개의 단어 중 ‘좋은 단어’의 개수를 세는 문제입니다.
풀이
이 문제는 괄호 짝 맞추기 문제와 유사하게 Stack (스택)을 활용하여 해결할 수 있습니다.
‘좋은 단어’의 조건인 “선들이 교차하지 않으면서 같은 글자끼리 짝을 짓는다”는 것은, 가장 최근에 등장한 미완성된 짝이 현재 글자와 짝을 이룰 수 있는지 확인하는 과정으로 바꾸어 생각해볼 수 있습니다.
단어를 순회하면서 각 문자에 대해 다음 규칙을 적용합니다:
- 스택이 비어있지 않고, 스택의 맨 위에 있는 문자가 현재 문자와 동일하다면 → 이는 현재 문자가 스택 맨 위의 문자와 짝을 이룰 수 있음을 의미합니다. 이 두 문자가 짝을 이루고 사라진다고 생각하여 스택에서 해당 문자를
pop합니다. - 그렇지 않다면 (스택이 비어있거나, 스택 맨 위의 문자가 현재 문자와 다르다면) → 현재 문자는 아직 짝을 찾지 못한 상태이므로, 스택에
push하여 짝을 기다리게 합니다.
모든 문자를 처리한 후, 스택이 비어있다면 모든 문자가 유효하게 짝을 지었다는 의미이므로 ‘좋은 단어’입니다. 만약 스택에 문자가 남아있다면, 짝을 찾지 못한 문자가 있다는 의미이므로 ‘좋은 단어’가 아닙니다.
이 과정을 각 단어에 적용하고, ‘좋은 단어’의 개수를 세어 최종 출력합니다.
정답 코드
def is_good_word(word):
stk = []
for ch in word:
if stk and stk[-1] == ch:
stk.pop()
else:
stk.append(ch)
return not stk
words = [input() for _ in range(int(input()))]
print(sum([1 for word in words if is_good_word(word)]))