[백준][17413] - 단어 뒤집기 2 python 파이썬

단어 뒤집기 2 - 17413

문제 링크

17413번: 단어 뒤집기 2

분류

자료 구조, 구현, 스택, 문자열

문제 설명

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

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

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

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

입력

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

출력

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

---

🙋 문제 해석

• 스택을 이용해서 문자열이 들어왔을 때 반대로 출력합니다.
• < 이나 > 같은 태그가 들어올 경우엔 정자로 출력합니다.

 

이 문제는 스택을 안다고 가정하여도 구현이 가장 중요합니다. 어떤 순서로 코드를 작성할 지 생각하고 하나씩 지워가면서 풀어가면 됩니다. flag로 구분하여 결과값을 저장하였습니다.

---

🔑 Solution 🔑

from collections import deque
a = input()+'\n' # 사용자로부터 문자열을 입력받음
flag = False # flag 변수 초기화
stack = deque() # deque() 함수를 사용하여 스택(Stack)을 생성
result = '' # 결과값을 저장할 변수 초기화

for i in a: 
    if not flag: 
        if i == '\n' or i == ' ': # 공백이나 개행 문자인 경우
            while stack: 
                result += stack.pop() 
            result += " " 

        else: # "<"와 ">" 사이에 있는 문자열이 아닌 경우
            if i == "<": 
                while stack: # 이 부분이 중요합니다.
                    result += stack.pop() 
                flag = True 

            stack.append(i) # 스택(Stack)에 데이터를 추가

    else: # flag가 True인 경우
        flag = True # flag를 True로 유지
        stack.append(i) 
        if i == ">": 
            while : stack: 
                result += stack.popleft() # 스택(Stack)에서 데이터를 popleft()하여 결과값에 추가
            flag = False 

print(result) # 결과값을 출력

---

🕐 시간 복잡도

 

시간복잡도 O(n)

• 시간 복잡도는 입력된 문자열의 길이가 n이라고 할 때, O(n)이다.
• 문자열의 각 문자를 하나씩 확인하면서 스택(Stack)에 추가하거나 제거하므로, 한 번 문자열의 모든 문자를 확인하는 과정에서 스택(Stack)에 대한 연산은 모두 O(1)의 시간 복잡도를 가지기 때문
• 문자열의 길이에 비례하여 시간 복잡도가 증가하므로 O(n)

---

🙇