💻 백준 17413번: 단어 뒤집기 2

문제 소개 🧐

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

  1. 알파벳 소문자(‘a’-‘z’), 숫자(‘0’-‘9’), 공백(‘ ‘), 특수 문자(‘<’, ‘>‘)로만 이루어져 있다.
  2. 문자열의 시작과 끝은 공백이 아니다.
  3. ’<‘와 ‘>‘가 문자열에 있는 경우 번갈아가면서 등장하며, ‘<‘이 먼저 등장한다. 또, 두 문자의 개수는 같다.

태그는 ‘<‘로 시작해서 ‘>‘로 끝나는 길이가 3 이상인 부분 문자열이고, ‘<‘와 ‘>’ 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

입력 📝

첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.

출력 📤

첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.

제한 ❌

  • 시간 제한: 1초
  • 메모리 제한: 512MB

첫 번째 시도: Deque를 활용한 풀이 ✨

Idea

문자열을 순회하면서 태그(<...>)의 안과 밖을 구분하는 플래그(is_open)를 사용했다.

  • 태그가 열리면 (<), 플래그를 True로 설정하고, 그전까지 쌓아둔 단어를 뒤집어서 결과에 추가했다.
  • 태그가 닫히면 (>), 플래그를 False로 설정했다.
  • 태그 안에서는 문자를 그대로 Deque에 넣었다가 순서대로 빼서 결과에 추가했다.
  • 태그 밖에서는 문자를 Deque에 넣고, 공백을 만나거나 태그를 만나거나 문자열 끝에 도달하면 Deque의 내용을 뒤집어서 (pop) 결과에 추가했다.

이러한 방식으로 Deque의 pop()과 popleft()를 적절히 활용하여 문제를 해결했다.

Code

import sys
from collections import deque

s = list(sys.stdin.readline().rstrip())
# <ab cd>ef gh<ij kl>

deq = deque()
is_open = False
answer = ''
for i in range(len(s)):
    if s[i] == '<':
        is_open = True
        while deq:  # 열린 꺽쇠 전까지 위에서부터 print
            letter = deq.pop()
            answer += letter
    deq.append(s[i])
    if not is_open and s[i] == ' ':  # 꺽쇠 안에 있지 않으면서 space
        deq.pop()
        while deq:
            letter = deq.pop()
            answer += letter
        answer += ' '
    if s[i] == '>':  # 꺽쇠 닫힌 경우
        is_open = False
        while deq:
            letter = deq.popleft()
            answer += letter

while deq:
    letter = deq.pop()
    answer += letter

print(answer)

Result

  • 결과: 성공! 🎉
  • Deque 자료구조의 특성을 활용하여 태그 내부의 문자는 순서대로, 단어는 역순으로 효율적으로 처리할 수 있었다.

배운 점 및 개선할 부분 🤔

  • 상태 관리의 중요성: 태그의 내부와 외부라는 두 가지 상태를 명확히 구분하고 각 상태에 맞는 로직을 처리하는 것이 문제 해결의 핵심이었다.
  • 자료구조의 적절한 활용: Deque는 앞과 뒤에서 데이터를 추가하거나 제거하는 데 O(1) 시간이 걸리므로, 스택과 큐의 역할을 동시에 수행해야 하는 이번 문제에 매우 적합한 자료구조였다. 단어를 뒤집을 때는 스택처럼(pop), 태그를 처리할 때는 큐처럼(popleft) 사용하여 코드를 간결하게 작성할 수 있었다.

상태에 따라 다르게 동작하는 로직을 구현할 때, 플래그를 이용한 상태 관리 기법이 유용하다는 것을 다시 한번 확인할 수 있었다.

⁂