[스택] 코딩테스트 문제 TIL (단어 뒤집기) - 백준 9093번

안녕하세요!!

오늘 문제는 백준 9093번, 단어 뒤집기 문제입니다.

코테는 쉽지않지만 오늘도 발전해봅시다. 문제 들어가볼까요?

---

1. 오늘의 학습 키워드

• 구현
• 문자열
• 스택

---

2. 문제: 단어 뒤집기 (9093번)

• 단계: 🥉브론즈 1티어
• 알고리즘 분류: 구현, 문자열, 스택
• 출처: https://www.acmicpc.net/problem/9093

단어 뒤집기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	41110	22049	16666	54.598%

문제

문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.

예제 입력 1 복사

2
I am happy today
We want to win the first prize

예제 출력 1 복사

I ma yppah yadot
eW tnaw ot niw eht tsrif ezirp

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 PA번

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 구현
• 문자열

---

3. 나의 풀이

3.1 스택을 활용한 풀이

이 방법은 스택 자료구조를 활용하여 각 단어를 뒤집는 방식입니다. 스택은 LIFO(Last In, First Out) 구조를 가지고 있기 때문에, 단어의 문자를 스택에 하나씩 넣고, 공백을 만났을 때 스택에서 문자를 하나씩 꺼내어 단어를 뒤집어 출력할 수 있습니다.

코드 설명:

import sys
from collections import deque

T = int(sys.stdin.readline().strip())

for _ in range(T):
    sentences = sys.stdin.readline().strip()
    sentences += ' '  # 마지막 단어를 뒤집기 위해 공백 추가

    stack = deque()

    for j in sentences:
        if j != " ":
            stack.append(j)  # 단어의 문자를 스택에 넣음
        else:
            while stack:
                print(stack.pop(), end='')  # 스택에서 문자를 꺼내어 뒤집기
            print(' ', end='')  # 단어 간의 공백 출력
    print()

장점:

• 스택 자료구조를 이용해 단어를 뒤집는 직관적인 방식으로, 공백을 기준으로 문자를 뒤집는 과정을 쉽게 구현할 수 있습니다.
• 스택을 이용해 단어를 뒤집는 알고리즘을 이해하는 데 도움이 됩니다.

단점:

• 스택을 사용하기 때문에 추가적인 메모리 사용이 필요합니다. 하지만 입력 크기가 작아 성능에 큰 영향을 미치지는 않습니다.

3.2 문자열 슬라이싱을 활용한 풀이

이 방법은 Python의 문자열 슬라이싱 기능을 활용하여 단어를 뒤집는 방식입니다. Python의 슬라이싱 기능을 사용하면 손쉽게 문자열을 뒤집을 수 있습니다.

코드 설명:

import sys

T = int(sys.stdin.readline().strip())

for _ in range(T):
    sentences = sys.stdin.readline().split()  # 공백을 기준으로 문장을 단어로 나눔

    for i in sentences:
        print(i[::-1], end=' ')  # 각 단어를 뒤집어서 출력
    print()

• 코드가 간결하고 직관적입니다. Python의 강력한 슬라이싱 기능을 활용하여 단어를 쉽게 뒤집을 수 있습니다.
• 추가 메모리 사용이 거의 없으며, 매우 빠르게 실행됩니다.

저도 처음에는 두 번째 방법을 사용해서 접근을 했습니다. 하지만 스택 유형으로도 풀 수 있는 문제입니다!

---

4. 시간 복잡도 분석

4.1 스택을 활용한 풀이

이 방법은 각 단어의 문자를 스택에 쌓고, 공백을 만날 때마다 스택에서 문자를 꺼내어 단어를 뒤집습니다.

• 문자열의 길이: 입력된 문장의 길이를 n이라고 할 때, 이 방법은 문장의 모든 문자를 한 번씩 순회합니다.
• 스택 연산: 각 문자에 대해 스택의 append 연산(삽입)은 $O(1)$의 시간 복잡도를 가지며, 공백을 만났을 때 스택에서 문자를 꺼내는 pop 연산도 $O(1)$입니다.

따라서, 전체 알고리즘의 시간 복잡도는 $O(n)$입니다.

4.2 문자열 슬라이싱을 활용한 풀이

이 방법은 Python의 슬라이싱 기능을 사용하여 각 단어를 뒤집습니다.

• 문자열의 길이: 문장을 단어 단위로 나눈 후, 각 단어를 슬라이싱하여 뒤집습니다. 이 과정에서 모든 문자를 한 번씩 처리합니다.
• 슬라이싱 연산: Python의 슬라이싱 연산은 각 단어의 길이에 비례한 $O(m)$의 시간 복잡도를 가지며, 여기서 m은 단어의 길이입니다.

결과적으로, 전체 알고리즘의 시간 복잡도는 $O(n)$입니다. 여기서 n은 문장 전체의 길이로, 모든 단어의 길이 합에 해당합니다.

두 방법 모두 시간 복잡도가 $O(n)$으로 동일합니다. 그러나 구현의 간결성과 메모리 사용 측면에서 차이가 있습니다.

• 스택을 활용한 방법: 스택을 사용해 단어를 뒤집는 과정이 명확하게 드러나며, 자료구조를 이해하는 데 도움이 됩니다. 다만, 스택을 사용하기 때문에 약간의 추가 메모리 사용이 발생합니다.
• 문자열 슬라이싱을 활용한 방법: 코드가 더 간결하며 Python의 강력한 기능을 활용할 수 있습니다. 메모리 사용도 최소화할 수 있습니다.

각 상황에 맞게 두 방법 중 적합한 것을 선택하면 좋습니다.

---

마무리

이번 문제에서는 두 가지 접근 방식을 활용하여 단어를 뒤집는 문제를 해결했습니다. 스택을 활용한 방식과 문자열 슬라이싱을 활용한 방식은 각각의 장단점이 있습니다. 스택을 활용한 방식은 자료구조의 활용을 이해하는 데 도움이 되며, 문자열 슬라이싱을 활용한 방식은 Python의 기능을 효율적으로 사용하는 방법을 보여줍니다.

두 가지 방법 모두 단어를 뒤집는 문제를 효과적으로 해결할 수 있으므로, 상황에 따라 적합한 방법을 선택하면 좋을 것 같습니다.

읽어주셔서 감사합니다!

Let’s keep going! ⭐