안녕하세요!!
곧 바빠질 예정이라 오늘 다른 문제를 또 가지고 왔습니다. 코테는 연습, 반복만이 살 길! 모두 아시죠?
1. 오늘의 학습 키워드
- 문자열
- 구현
- 스택
2. 문제: 단어 뒤집기 2 (17413번)
- 단계: 🥈실버 3티어
- 알고리즘 분류: 구현, 자료 구조, 문자열, 스택
- 출처: https://www.acmicpc.net/problem/17413
단어 뒤집기 2
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 34160 | 19244 | 14973 | 56.789% |
문제
문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.
먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.
- 알파벳 소문자('
a'-'z'), 숫자('0'-'9'), 공백(' `'), 특수 문자('<', '>`')로만 이루어져 있다. - 문자열의 시작과 끝은 공백이 아니다.
- '
<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.
태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.
입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.
출력
첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.
예제 입력 1 복사
baekjoon online judge
예제 출력 1 복사
noojkeab enilno egduj
예제 입력 2 복사
<open>tag<close>
예제 출력 2 복사
<open>gat<close>
예제 입력 3 복사
<ab cd>ef gh<ij kl>
예제 출력 3 복사
<ab cd>fe hg<ij kl>
예제 입력 4 복사
one1 two2 three3 4fourr 5five 6six
예제 출력 4 복사
1eno 2owt 3eerht rruof4 evif5 xis6
예제 입력 5 복사
<int><max>2147483647<long long><max>9223372036854775807
예제 출력 5 복사
<int><max>7463847412<long long><max>7085774586302733229
예제 입력 6 복사
<problem>17413<is hardest>problem ever<end>
예제 출력 6 복사
<problem>31471<is hardest>melborp reve<end>
예제 입력 7 복사
< space >space space space< spa c e>
예제 출력 7 복사
< space >ecaps ecaps ecaps< spa c e>
출처
- 문제를 만든 사람: baekjoon
알고리즘 분류
3. 나의 풀이
이 문제는 문자열에서 태그와 단어를 구분하여 처리해야 합니다. 태그(<...>) 내부의 내용은 그대로 두고, 태그 외부의 단어들만 뒤집어야 합니다. 이 문제를 해결하기 위해서는 문자열을 한 문자씩 읽어가면서 태그와 단어를 구분하고, 스택을 사용하여 단어를 뒤집는 방식으로 접근할 수 있습니다.
접근 방식:
- 태그 구분:
<로 시작해서>로 끝나는 태그는 그대로 출력해야 하므로, 태그가 시작되면tag변수를True로 설정하고, 태그가 끝나면False로 설정합니다. - 단어 뒤집기: 태그 외부에서 만나는 단어들은 스택에 하나씩 쌓아두었다가, 공백이나 태그를 만났을 때 스택에서 꺼내어 뒤집어서 출력합니다.
- 공백 처리: 단어와 단어를 구분하는 공백은 그대로 결과에 추가하며, 공백을 만났을 때 이전에 쌓인 단어를 뒤집어 출력합니다.
코드 설명:
import sys
from collections import deque
S = sys.stdin.readline().strip()
stack = deque()
result = ''
tag = False
for i in S:
if i == '<': # 태그의 시작
while stack:
result += stack.pop() # 스택에 쌓인 단어를 뒤집어서 추가
tag = True
result += i # 태그 시작 '<'를 결과에 추가
elif i == '>': # 태그의 끝
tag = False
result += i # 태그 끝 '>'를 결과에 추가
elif tag: # 태그 내부
result += i # 태그 안의 문자는 그대로 추가
elif i == ' ': # 공백을 만날 때
while stack:
result += stack.pop() # 스택에 쌓인 단어를 뒤집어서 추가
result += i # 공백을 그대로 추가
else:
stack.append(i) # 단어를 스택에 쌓음
# 마지막 단어 처리 (스택에 남아 있는 경우)
while stack:
result += stack.pop()
print(result)
코드 동작:
- 태그 시작
<: 태그가 시작되면, 그 전까지 쌓인 단어를 뒤집어 결과에 추가한 후, 태그 안의 내용을 그대로 출력합니다. - 태그 종료
>: 태그가 끝날 때까지 태그 안의 문자를 그대로 출력하고, 태그가 끝나면 다시 단어를 뒤집는 모드로 전환합니다. - 공백: 단어와 단어 사이의 공백을 만나면 스택에 쌓인 단어를 뒤집어 출력하고, 공백 자체도 결과에 추가합니다.
- 단어: 태그 밖에 있는 단어의 각 문자를 스택에 쌓아두다가, 뒤집어 출력합니다.
- 마지막 단어 처리: 문자열 끝에 도달했을 때, 스택에 남아 있는 단어가 있으면 그것을 뒤집어서 출력합니다.
결과:
이 코드로 주어진 문제에서 요구하는 대로 태그는 그대로 유지하면서, 태그 외부의 단어만 뒤집어서 출력할 수 있습니다.
시간 복잡도:
이 코드의 시간 복잡도는 문자열의 길이 n에 대해 입니다. 각 문자를 한 번씩만 처리하며, 스택의 pop 연산은 이기 때문에 매우 효율적입니다.
마무리
오늘은 백준 17413번, "단어 뒤집기 2" 문제를 통해 문자열을 다루는 방법과 스택을 활용한 문제 해결 방식을 연습해보았습니다. 이 문제는 단순히 문자열을 뒤집는 것이 아니라, 태그와 단어를 구분하여 처리해야 하기 때문에 좀 더 섬세한 접근이 필요했습니다.
이처럼 하나의 문제를 다양한 방법으로 해결하는 경험은 코딩 테스트에서 매우 중요합니다. 알고리즘 문제를 풀다 보면 처음에는 복잡해 보이지만, 반복 연습과 다양한 접근 방식을 통해 점점 더 효율적인 해결 방법을 찾을 수 있습니다.
코딩 테스트는 꾸준한 연습과 반복만이 답입니다! 아직 한참 부족한 저이지만 전 끊임없이 노력할 것입니다.
다음에 더 흥미로운 문제로 다시 만나요! 감사합니다. 🚀
