문제
문자열 S가 주어졌을 때, 태그(< 와 > 사이의 문자열) 안의 내용은 그대로 유지하고, 태그 밖의 단어(공백으로 구분)는 각각 뒤집어 출력하는 문제다.
입력
- 첫째 줄: 문자열 S (길이 1 이상 100,000 이하, 알파벳 소문자, 숫자, 공백,
<,>로 구성)
출력
조건에 맞게 변환한 문자열을 출력한다.
예제
| 입력 | 출력 |
|---|---|
baekjoon online judge | nooJkeab enilno egduj |
<tag>baekjoon</tag> | <tag>nooJkeab</tag> |
풀이
<와 >, 공백을 구분자로 삼아 세 가지 상태를 플래그로 관리하며 단어 뒤집기를 수행한다.
flag = false(태그 밖) 상태로 시작하며 문자열을 한 글자씩 순회한다.<를 만나면 현재까지 쌓인tmp버퍼를 뒤집어 결과에 추가하고,flag = true로 변경 후<를 결과에 추가한다.flag = true(태그 안)이면 문자를 그대로 결과에 추가한다.>를 만나면flag = false로 변경한다.- 태그 밖에서 공백을 만나면
tmp버퍼를 뒤집어 결과에 추가하고 공백을 결과에 추가한다. - 그 외 문자는
tmp버퍼에 누적한다. - 순회 완료 후
tmp에 남은 내용을 뒤집어 결과에 추가한다.
핵심 아이디어: 태그 감지를 위한 boolean flag를 두고 </> 경계에서 버퍼를 뒤집는 방식으로 한 번의 순회(O(N))에 처리한다. StringBuilder를 활용해 문자열 뒤집기를 직접 구현했다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day08BOJ17413단어뒤집기2 { // 17413번 글자 뒤집기 2
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringBuilder tmp = new StringBuilder();
String str = br.readLine();
// 공백과 <, >을 만날 때마다 조건
boolean flag = false;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '<') {
tmp = reverSe(tmp);
sb.append(tmp);
tmp = new StringBuilder();
flag = true;
}
if (flag == true)
sb.append(c); // 정방향 입력
if (c == '>') // >까지 넣고 불린값 변경
flag = false;
if (c != '>' && flag == false) {
if (c == ' ') {
tmp = reverSe(tmp);
sb.append(tmp);
sb.append(c);
tmp = new StringBuilder();
} else
tmp.append(c);
}
}
tmp = reverSe(tmp);
sb.append(tmp);
System.out.println(sb);
}
private static StringBuilder reverSe(StringBuilder tmp) {
String str = tmp.substring(0);
tmp = new StringBuilder();
for (int i = str.length() - 1; i >= 0; i--) {
tmp.append(str.charAt(i));
}
return tmp;
}
}복잡도
- 시간: O(N) — 문자열을 한 번 순회하며 처리
- 공간: O(N) — 결과 버퍼와 임시 버퍼