Algorithms

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

짤진이 2024. 10. 10. 19:02
반응형

문제 링크

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

 

문제 이해

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

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

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

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

입력

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

출력

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

 

 

후위연산 문제를 풀고 난 이후에 이 문제를 보니 이해가 쉬웠다.

여러가지의 조건을 전부 만족할때까지 stack에 추가하거나 answer에 바로 더해주거나 stack에서 pop하는 구조이다.

 

조건 1) <가 들어왔을 경우

<가 들어왔을 때 stack에 값이 있는지 없는지를 판별해야한다.

<aaa>aaa<aaa> 구조일 때,

처음 <aaa>에서는 stack에 값이 없으므로 answer에 바로 더해주면 되지만,

두번째 <aaa>에서는 태그 사이의 값(stack 값)이 있기 때문에 stack이 없어질 때까지 전부 pop해준다.

전부 pop한 후에 다시 <를 tmp에 삽입하고 answer에 더해준다.

조건 2) 알파벳 혹은 숫자가 들어왔을 경우

만약 <가 들어가 있어서 tmp에 값이 있다면 태그 내의 값이므로 answer에 바로 더해준다.

하지만 반대 조건이라면 태그 내의 값이 아니므로 스택에 전부 추가해준다.

 

조건 3) " ", 공백 문자가 들어왔을 경우

tmp에 < 값이 없을 경우는 태그 내의 값이므로 stack에 있는 값을 전부 pop해준다.

 

조건 4) >가 들어왔을 경우

tmp에 들어가있던 < 값을 pop해주고 answer에 > 값을 더해준다.

 

차근차근 조건을 따지면서 while 문을 적절히 활용하여 pop해준다면 간단히 해결할 수 있던 문제였다.

코드

import sys
alphas = sys.stdin.readline()
stack = []
tmp = []
answer = ""
for alpha in alphas:
  if alpha == "<":
    while stack:
      answer += stack.pop()
    tmp.append(alpha)
    answer += alpha
  elif alpha.isalpha() or alpha.isdigit():
    if tmp:
      answer += alpha
    else:
      stack.append(alpha)
  elif alpha == " ":
    if len(tmp) == 0:
      while stack:
        answer += stack.pop()
    answer += alpha

  elif alpha == ">":
    tmp.pop()
    answer+= alpha
while stack:
  answer += stack.pop()
print(answer)
반응형