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

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

 

 

사용 알고리즘: 큐

 

 

입력

• 문자열 S 가 주어짐 (S 의 길이는 100,000 이하)

 

규칙

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

태그는 '<' 로 시작해서 '>' 로 끝나는 3 이상인 부분 문자열이고, '<' 와 '>' 사이에는 알파벳 소문자와 공백만 있다. 

단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 

태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다. 

 

 

예제 입력 1

baekjoon online judge

 

예제 출력 1

noojkeab enilno egduj

 

예제 입력 2

<open>tag<close>

 

예제 출력 2

<open>gat<close>

 

예제 입력 3

<ab cd>ef gh<ij kl>

 

예제 출력 3

<ab cd>fe hg<ij kl>

 

 

단어는 뒤집어서 출력해야 하고, 태그는 그대로 출력해야 함 -> deque (데크)

 

앞뒤로 빼는 것이 가능해야 하기 때문에 데크를 사용했다.

 

- 데크란?

 

 

사용 함수

# 태그 출력 함수
def printTag(q):
    while q:
        print(q.popleft(), end='')

# 단어 출력 함수
def printWord(q):
    while q:
        print(q.pop(), end='')

 

 

고려해야 할 케이스

• 단어는 공백으로 구분된다고 했는데, 태그 안에 공백이 있는 경우 

위의 경우를 처리하기 위해 pre 라는 변수를 둬서 '<' 를 만나면 pre 를 1 로 바꾸어 데크 안에 '<' 가 들어있는지 없는지 확인할 수 있도록 했다. 

• pre = 1 일 때 공백이 나오면 데크 안에 '<' 이 들어있다는 것이므로 태그로 취급
• pre = 0 일 때 공백이 나오면 단어로 취급

# '<'이 데크에 들어있는지 확인할 수 있는 변수
# 0 이면 없음, 1 이면 있음
pre = 0

for x in string:
    if x == '<':
        pre = 1 # 데크 안에 '<' 있음을 표시
        printWord(deque) # 이전까지 데크에 들어있던 단어를 print
        deque.append(x)
    elif x == '>' and pre == 1: # 데크 안에 '<' 있음 -> 태그
        printTag(deque)
        print(x, end='')
        pre = 0 # 처리 후 다시 0
    elif x == ' ' and pre == 0: # 데크 안에 '<' 없음 -> 단어
        printWord(deque)
        print(x, end='')
    else: # 그 외에는 데크에 추가
        deque.append(x) #

# 마지막에 데크에 남아있는 단어 print
printWord(deque)

 

 

 

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

# 입력
string = list(input().strip())

deque = deque()

# 태그 출력 함수
def printTag(q):
    while q:
        print(q.popleft(), end='')

# 단어 출력 함수
def printWord(q): 
    while q:
        print(q.pop(), end='')

# '<'이 데크에 들어있는지 확인할 수 있는 변수
# 0 이면 없음, 1 이면 있음
pre = 0

for x in string:
    if x == '<':
        pre = 1 # 데크 안에 '<' 있음을 표시
        printWord(deque)
        deque.append(x)
    elif x == '>' and pre == 1: # 데크 안에 '<' 있음 -> 태그
        printTag(deque)
        print(x, end='')
        pre = 0 # 처리 후 다시 0
    elif x == ' ' and pre == 0: # 데크 안에 '<' 없음 -> 단어
        printWord(deque)
        print(x, end='')
    else: # 그 외에는 데크에 추가
        deque.append(x)

printWord(deque)