99클럽 코테 스터디 9일차 TIL

문제

BOJ 3986 - 좋은 단어

🔍 문제 요약

• 문자열에서 같은 알파벳끼리 짝을 지어야 함
• 선이 교차하지 않도록, 즉 스택 구조처럼 처리해야 함
• 모든 문자가 정확히 한 번만 짝지어지면 → "좋은 단어"

📌 풀이 전략:

• 문자를 하나씩 순회하며:
  • 스택이 비었거나 top이 다르면 → append()
  • top과 현재 문자가 같으면 → pop()
• 단어 순회 후 스택이 비어 있으면 → 좋은 단어로 카운트
• python에는 peek()이 없으므로, 배열 마지막 요소를 확인하는 것으로 대체

👩‍💻 코드

import sys

n = int(sys.stdin.readline())
count = 0

for _ in range(n):
    word = sys.stdin.readline().strip()
    stack = []
    for c in word:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    if not stack:
        count += 1

print(count)

 

⏱ 시간 복잡도

O(n × m): (n = 단어 수, m = 평균 단어 길이)

💾 공간 복잡도

O(m) (입력 문자열 한 줄씩 처리 → 리스트 저장 없이 공간 최소화) or O(m * n)

💡 배운 점

• 스택 문제는 짝짓기 문제랑 매우 밀접함 (ex: 괄호, 알파벳, 연산자 등)
• 입력을 한 줄씩 처리하면 불필요한 공간 사용 줄일 수 있음 (백준에서 이런거 되는지 몰랐음)
• str 같은 내장 타입 이름은 변수명으로 쓰지 않기

조금의 개선사항

• 첫 코드는 O(n × m) + 저장용 리스트로 메모리 조금 더 씀
• 개선된 버전은 저장 없이 바로 처리 → 메모리가 그렇게 크게..줄지는 않음!