[Python] 백준 17413번_단어 뒤집기 2

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

17413번: 단어 뒤집기 2

 

• 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 함
• 문자열 S는 아래와과 같은 규칙을 지킴
  • 1) 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있음
  • 2) 문자열의 시작과 끝은 공백이 아님
  • 3) '<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장. 두 문자의 개수는 같음
• 태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있음
• 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분
• 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없음

• 입력
  • 첫째 줄에 문자열 S가 주어짐. S의 길이는 100,000 이하
• 출력
  • 첫째 줄에 문자열 S의 단어를 뒤집어서 출력
• 시간 제한: 1초
• 메모리 제한: 512 MB

 

"""
입출력 예시)

(예제 입력 1) 
baekjoon online judge -> noojkeab enilno egduj

(예제 입력 2)
<open>tag<close> -> <open>gat<close>

(예제 입력 3)
<ab cd>ef gh<ij kl> -> <ab cd>fe hg<ij kl>

(예제 입력 4)
one1 two2 three3 4fourr 5five 6six -> 1eno 2owt 3eerht rruof4 evif5 xis6

(예제 입력 5)
<int><max>2147483647<long long><max>9223372036854775807 -> <int><max>7463847412<long long><max>7085774586302733229

(예제 입력 6)
<problem>17413<is hardest>problem ever<end> -> <problem>31471<is hardest>melborp reve<end>

(예제 입력 7)
<   space   >space space space<    spa   c e> -> <   space   >ecaps ecaps ecaps<    spa   c e>
"""

 

 

## 의사코드 ##

# 단어만 뒤집기 
# -> 태그인 < > 사이의 문자열은 뒤집기 x

# stack 생성
# 단어인 경우에만 알파벳 하나씩 스택에 삽입
# 스택.pop()으로 단어 거꾸로 출력

# tag == True인 경우
# 그대로 출력

 

 

 

통과한 코드

 

string = str(input())
stack = []
tag = False
result = ''

for s in string:
    # 공백인 경우
    if s == ' ':
        # stack에서 pop -> 거꾸로 출력
        while stack:
            result += stack.pop()
        result += s
    # 태그 시작인 경우
    elif s == '<':
        # 태그 사이에 있는 단어 거꾸로 출력 
        while stack:
            result += stack.pop()
        tag = True
        result += s
    # 태그 끝인 경우  
    elif s == '>':
        tag = False # 태그 = False 
        result += s 
    # 태그인 경우 
    elif tag:
        result += s # 그대로 출력
    # 공백이 아니거나 태그 밖의 단어인 경우   
    else:
        stack.append(s) # stack에 삽입 

while stack:
    result += stack.pop()
    
print(result)

-> 태그 사이에 있는 단어를 거꾸로 출력하기 위해서는 s == "<" 인 경우에 먼저 stack을 비워줘야 함

 

 

• 과정 확인

string = "<open>tag<close>"

"""
s: <
stack: []
result: <
s: o
result: <o
s: p
result: <op
s: e
result: <ope
s: n
result: <open
s: >
result: <open>
s: t
stack: ['t']
s: a
stack: ['t', 'a']
s: g
stack: ['t', 'a', 'g']
s: <
stack: ['t', 'a', 'g']
result: <open>g
result: <open>ga
result: <open>gat
result: <open>gat<
s: c
result: <open>gat<c
s: l
result: <open>gat<cl
s: o
result: <open>gat<clo
s: s
result: <open>gat<clos
s: e
result: <open>gat<close
s: >
result: <open>gat<close>
stack: []
<open>gat<close>
"""

 

 

 

 

 

참고)

 

https://star7sss.tistory.com/391

[자료구조/스택] 백준 17413 단어 뒤집기 2 - 파이썬(Python)