처음에는 해당 문제를 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로 훨씬 줄어든 것을 확인할 수 있다.
'Algorithm > Data Structure' 카테고리의 다른 글
[백준] 17298: 오큰수 (python 파이썬) (0) | 2024.04.28 |
---|---|
[백준] 10799: 쇠막대기 (python 파이썬) (2) | 2024.04.28 |
[백준] 10866: 덱 (python 파이썬) (2) | 2024.04.07 |
[백준] 10845: 큐 (python 파이썬) (0) | 2024.04.06 |
[백준] 1406: 에디터 (python 파이썬) (0) | 2024.04.05 |