[Python] 17413번 단어 뒤집기 2

https://www.acmicpc.net/problem/17413

17413번: 단어 뒤집기 2

---

 

22/09/14

 

 

조금 귀찮았던 문자열 문제로, 스택을 이용하여 문제를 접근했다.

---

 

문제 접근 방식:

 

 

문제 자체는 간단하다.

 

공백을 기준으로 단어가 정해지는데, 원래 문자열이 주어지면 단어만 전부 뒤집어서 출력해주는 문제이다.

 

나는 뒤집는다는 점에 주목하여 문자 하나하나를 스택에 담다가 공백을 만나면 그 스택을 뒤집어서 전부 출력하는 것으로 접근했다.

 

하지만 여기에서 귀찮은 구현이 하나가 추가가 되는데, 꺾쇠괄호가 바로 그것이다.

꺾쇠괄호 안에 있는 문자열은 안에 공백이 있든 어쩌든 간에 다 무시하고 뒤집어주지 않고 그대로 출력해준다.

따라서 꺾쇠 괄호를 출력하려면 스택을 그대로 출력해주어야 한다.

 

'일반 문자열'과 '꺾쇠괄호가 있는 문자열' 두 개를 각각 다루는 '일반 스택'과 '꺾쇠 스택'을 사용하여 구현하기로 했다.

 

문자열의 원소 하나하나씩을 돌며 만약 그 원소가 열린 꺾쇠라면 지금까지 담겨 있던 '일반 스택'을 출력해주고, 그 부분부터 꺾쇠 스택에 차곡차곡 담아주었다.

 

닫힌 꺾쇠라면지금까지 꺾쇠 스택에 담겼던 문자열(꺾쇠를 포함한 꺾쇠 안에 있는 문자들)을 한꺼번에 출력해주기로 하였다.

 

일반적인 문자면서 꺾쇠 스택이 현재 차있지 않은 상태라면 그 문자를 일반 스택에 담아주었다.

일반적인 문자면서 꺾쇠 스택에 뭔가가 있다면 괄호가 열린 것이므로 그 문자는 꺾쇠 스택에 담아주었다.

 

만약 공백을 만나면 일반 스택을 거꾸로 출력해주는 것으로 생각했다.(뒤집어야 하므로)

 

그러니깐 맨 처음 생각했었을 때엔 스택을 한번 사용할 수 있는 문제를 두 번 사용하여 접근했던 것이었다.

 

그래서 스택을 줄여서 구현할 수 있지 않을까 생각하다가, 스택 한 개로 구현하는 방법을 생각했다.

 

앞에서는 공백을 만나면 일반 스택을 출력한다고 했는데, 사실 꺾쇠 스택이 차있을 때는 일반 스택이 항상 비어있다.

 

이를 이용하여, 그냥 공백이 아니라 공백이면서, 스택의 첫 번째 원소가 꺾쇠가 아닐 때, 다시 말해 괄호가 시작하지 않은 상태이고 공백을 만났다면 지금까지의 스택을 거꾸로 출력해주었다.

 

그리고 일반적인 문자열이면 그냥 스택에 담아주는 것으로 했다.

 

나머지는 똑같다. 다만 스택을 재사용하기 위해 중간에 스택을 비워주는 작업이 들어갔다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 17413번 단어 뒤집기 2
# 스택, 문자열
import sys
input = sys.stdin.readline

S = input().rstrip()
stack = []
for char in S:
    if char == '<':
        print(''.join(stack[::-1]), end = '')
        stack.clear()
        stack.append(char)
    elif char == '>':
        stack.append(char)
        print(''.join(stack), end = '')
        stack.clear()
    elif char == ' ' and stack[0] != '<':
        print(''.join(stack[::-1]), end = ' ')
        stack.clear()
    else:
        stack.append(char)
print(''.join(stack[::-1]), end = '')