Algorithm TIL (240906)

> [백준] 단어 뒤집기 2 (17413)

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

 

 

💡 문제 풀이 과정

• 문자열 s가 주어졌을 때, 규칙에 따라 단어인 경우에만 단어를 반대로 뒤집는다. 이 때 < 로 시작해서 >로 끝나는 문자열은 태그로 단어가 아니다.
• 처음에는 쉽게 생각했으나, 전체 문자열을 통으로 뒤집는 게 아니라, 특정 문자열의 길이만큼 뒤집어야 하는 것이라서 조금 헤맸다. 문제 접근 과정은 아래와 같다.

문제 아이디어

• 스택을 활용한 구현
• 동작
  • s 를 loop 순회하면서 i번째 문자열이 <이면 태그 이므로 flag를 세운다.
  • 그리고 < 이전에 stack에 쌓은 문자들을 다 pop하여 결과 문자열(ans)에 넣는다.
  • i번째 문자열은 stack에 넣는다.
  • s를 loop 순회하면서 i번째 문자열이 >이면 태그가 끝나는 것이므로 flag를 내린다.
  • 그리고 stack에 쌓은 문자들은 태그 안에 문자열이기 때문에 올바르게 출력해야 한다. 현재 stack을 거꾸로 하여 pop 하고 결과 문자열(ans)에 넣는다.
  • s를 loop 순회하면서 i번째 문자열이 공백이고 flag가 내려가 있는 경우는 태그가 아니므로 stack 내용을 거꾸로 출력해야 한다. stack 에 쌓은 문자들을 모두 pop하여 결과 문자열(ans)에 넣는다.
  • 마지막으로 s 순회 이후 stack에 남은 문자열이 있다면 예제 4번과 같은 경우로 stack에 남게 된다. 이 또한 함께 출력한다.

 

 

✅ 문제 풀이

python

# 문자열을 뒤집기 위해 스택자료구조를 사용 (스택은 선입 후출)
import sys
input = sys.stdin.readline

s = input().strip()
stack = []
ans = []
flag = False # 태그인지 여부

for idx, word in enumerate(s) :
    if word == '<' : # 태그 문자열을 만나면
        flag = True
        while stack : # 기존 스택을 모두 꺼낸다.
            temp = stack.pop()
            ans.append(temp)
        
    stack.append(word) # 문자를 스택에 넣는다.

    if word == '>' : # 현재 문자가 '>'면 태그가 끝났기 때문에 태그문자열들을 모두 꺼낸다.
        flag = False
        stack.reverse() # 스택에 넣으므로 태그를 뒤집는다.
        while stack : 
            temp = stack.pop()
            ans.append(temp)
    
    if word == ' ' and not flag : # 공백이거나 태그가 아닐 떄
        stack.pop() # 공백 제거
        while stack :
            temp = stack.pop()
            ans.append(temp)
        ans.append(' ') # 있던 공백 추가

# 공백 구분했을 때, 예제 4번의 경우, 마지막 6six 단어가 stack에 쌓였으나, >,<,공백 이 아니고 flag=False 이므로
# 스택에 남아있게 된다. 그래서 마지막의 경우에 남아있는 단어가 있다면 마지막 단어니까
# stack.pop 하여 ans에 넣어주었다.
if stack :
    while stack : 
        ans.append(stack.pop())
    
print(''.join(ans))

 

😄 회고 및 느낀점

문자열을 구현하는 문제를 많이 풀어봐야 겠다. 자료구조의 개념을 알고 있어도 구현하는 것이 어렵당