백준 17413번: 단어 뒤집기 2 (Python)

💡 0. 문제 이해

📌 문제 설명

문자열 S가 주어졌을 때, 단어만 뒤집고 태그는 그대로 출력하는 프로그램을 작성하는 문제입니다.

📝 문제의 주요 규칙

• 단어: 알파벳 소문자(a-z)와 숫자(0-9)로 구성.
• 태그: <로 시작하고 >로 끝나는 부분 문자열로, 태그 내부는 뒤집지 않고 그대로 출력.
• 공백: 단어 구분자이며, 단어마다 공백이 하나씩 존재.
• 태그 처리: <를 만나면 태그 모드로 전환하여 태그 안의 문자를 그대로 출력하고, >를 만나면 태그 모드를 해제.
• 단어 처리: 태그 외부에서는 단어를 역순으로 출력.

⚡ 중요한 추가 사항

• 문자열의 길이는 최대 100,000으로, **O(N)**의 시간 복잡도를 가지는 풀이가 필요합니다.
• 마지막 단어 출력을 위해 반복문 종료 후 스택에 남은 문자를 출력하는 추가 처리도 필요합니다.

---

🎯 1. 핵심 (문제를 풀기 위한 접근 전략)

🧩 1️⃣ 태그 구간 판별

• <를 만나면 태그 모드를 True, >를 만나면 False로 변경합니다.
• 태그 모드가 True인 동안은 모든 문자를 그대로 출력합니다.

🪟 2️⃣ 단어 역순 출력 (Stack 사용)

• 태그 외부에서 단어를 한 글자씩 **스택(stack)**에 넣습니다.
• 공백(' ') 또는 **태그 시작(<)**을 만나면 스택의 모든 문자를 pop()하여 역순으로 출력합니다.
• 반복문이 끝난 후에도 스택에 남아 있는 문자가 있다면 마지막 단어를 출력합니다.

🔄 3️⃣ 공백 처리

• 공백을 만나면 스택의 문자를 모두 출력한 후 공백을 출력합니다.

💡 4️⃣ 시간 복잡도 고려

• 각 문자를 한 번씩만 탐색하고, 스택 연산은 O(1)로 처리하여 **O(N)**의 시간 복잡도를 유지합니다.

---

📝 2. 내 코드

# 핵심 2가지
# 1. 태그(<>) 시작점과 끝 점의 flag 설정
# 2. "순서를 거꾸로" => stack => stack.pop()

s = input()
stack = []
tag_flag = False

for char in s:
    
    # 태그 시작
    if char == "<":    
        tag_flag = True
        while stack:    # 태그를 만나기 전까지 스택에 쌓아온 게 있다면 pop
            print(stack.pop(), end='')
        print(char, end='')
        
    # 태그 끝
    elif char == ">":    
        tag_flag = False
        print(char, end='')
        
    # 태그 내부
    elif tag_flag:    
        print(char, end='')
        
    # 태그 외부 + 공백
    elif char == " ":
        while stack:
            print(stack.pop(), end='')
        print(" ", end='')
        
    # 태그 외부 (단어 구성 중)
    else:
        stack.append(char)
        
# 마지막 단어(태그 외부 + 공백X = 스택에 쌓여있는 거)
while stack:
    print(stack.pop(), end='')

---

🔎 ✨ 코드 특징 요약 ✨

• ✅ 태그 내부와 외부를 정확히 구분하여 처리
• ✅ 스택을 이용한 단어 역순 출력
• ✅ O(N) 시간 복잡도로 효율성 확보