[백준] 17413: 단어 뒤집기 2 (python 파이썬)

17413번: 단어 뒤집기 2

처음에는 해당 문제를 collections 라이브러리의 deque 자료구조를 활용해서 풀었다. 알고리즘은 다음과 같다.

• 먼저 입력 받은 문자열을 리스트로 변환한다. (리스트로 변환하면 문자열의 각 문자가 원소로 리스트에 들어간다. 예를 들어, "abc" 문자열은 ['a', 'b', 'c']로 들어간다.)
• 만약 첫 번째 원소가 '<'라면 현재 탐색하고 있는 부분은 태그 부분이다. 따라서 '>'가 나올 때까지 문자를 합쳐준다. '>'가 나온 경우 탐색을 멈추고 태그 내용을 출력한다.
• 만약 첫 번째 원소가 '<'가 아니라면 현재 탐색하고 있는 부분은 단어 부분이다. 따라서 '<'가 나오거나 ' '가 나올 때까지 문자를 합쳐준다. ('<'가 나오면 새로운 태그가 시작되는 것이고, ' '가 나오면 새로운 문자가 시작되는 것을 의미하기 때문이다.) 단, 더 이상 탐색할 문자가 없으면 탐색은 종료한다.

해당 알고리즘을 활용해 코드를 작성하면 다음과 같다.

import sys
from collections import deque

input = sys.stdin.readline

char_queue = deque(input().rstrip())

while char_queue:
    string = ""
    if char_queue[0] == '<':
        while char_queue[0] != '>':
            string += char_queue.popleft()
        string += char_queue.popleft()
        print(string, end='')
    else:
        while len(char_queue) > 0 and char_queue[0] not in ['<', ' ']:
            string += char_queue.popleft()
        string = string[::-1]
        if len(char_queue) == 0 or char_queue[0] != ' ':
            print(string, end='')
        else:
            print(string, end=char_queue.popleft())

이렇게 문제를 풀면 304 ms 정도의 효율을 보인다. 하지만 위 문제를 수학적으로 접근하면 좀 더 빠르게 문제를 해결할 수 있다. 개선된 알고리즘은 다음과 같다.

• 현재 태그는 '<'와 '>'로 구성된다. 이때 이 둘을 동일한 한 개의 문자로 바꿔준다. ('>'를 '<'로 바꿔도 되고, 그냥 둘이 동일한 문자면 된다.)
• 만약 둘을 동일 문자로 바꿨다면 해당 문자로 문자열을 나눠준다.
• 위 과정을 거친다면 무조건 "홀수 인덱스"에 태그 문자가 오게 된다. 아래는 두 경우의 예시를 들고 있다.
  
  • 입력이 <open>close인 경우: 첫 번째 과정을 거치면 <open<close가 된다. 여기에 '<'로 문자를 나눠 리스트에 저장하면 ['', 'open', 'close']가 된다. (홀수 인덱스에  태그가 위치한다.)
  • 입력이 close<open>인 경우: 첫 번째 과정을 거치면 close<open<가 된다. 여기에 '<'로 문자를 나눠 리스트에 저장하면 ['close', 'open', '']가 된다. (홀수 인덱스에 태그가 위치한다.)

위 알고리즘을 통해 코드를 작성하면 다음과 같다.

import sys

input = sys.stdin.readline

strings_list = input().rstrip().replace('>', '<').split('<')
result = ""

for index, strings in enumerate(strings_list):
    if index%2 == 1:
        result += "<{}>".format(strings)
    else:
        result += ' '.join(string[::-1] for string in strings.split())
print(result)

알고리즘 시간은 44ms로 훨씬 줄어든 것을 확인할 수 있다.