백준 17413 <단어 뒤집기 2>

17413번: 단어 뒤집기 2 (acmicpc.net)

17413번: 단어 뒤집기 2

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

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

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

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

 

 

중요한점은 태그안에 녀석들은 뒤집히지 않는다. 

 

먼저 문자열 반전의 아이디어 :

자바에서 문자열을 반전하는 방법에는 여러 가지가 있습니다. 리스트에 담아서 reverse()를 사용하거나 스택에 넣어서 pop()을 사용하는 방법도 있습니다. 일반적인 효율성에 관해 이야기하자면, 그 차이는 상황에 따라 다를 수 있습니다.

1. 리스트에 추가하고 Collections.reverse()를 사용하는 방법: 이 방법은 일반적으로 빠른 성능을 제공합니다. 하지만, 문자열의 길이가 매우 긴 경우에는 리스트의 크기를 늘리는 데 시간이 더 소요될 수 있습니다.
2. 스택에 push하고 pop하는 방법: 이 방법은 일관된 성능을 제공합니다. 스택은 LIFO(Last In First Out) 속성을 가지므로, 자연스럽게 문자열을 반전시킬 수 있습니다. 하지만, 스택의 크기가 너무 커지면 메모리 문제가 발생할 수 있습니다.

따라서, 어떤 방법이 더 효과적인지는 사용하는 데이터의 크기와 상황에 따라 다를 수 있습니다. 또한, 문자열을 반전하는 것이 목적이라면, StringBuilder나 StringBuffer 클래스의 reverse() 메소드를 사용하는 것이 더 직관적이고 효율적일 수 있습니다. 이 메소드들은 내부적으로 문자 배열을 뒤집는 방식으로 동작하므로, 추가적인 자료구조를 사용하지 않아도 됩니다.

스택활용도 가능하며 list도 가능하다.

 

이 문제에서 스택을 활용한것은 저 태그 때문이다.

 

몇가지 조건문을 설정하면 문제가 쉽게 풀린다.

그 전에 만약 < > 이 태그 문자가 돌고있을때의 상태를 tag 라는 boolean type으로 생성한다.

1. tag가 false일때 - 

이때는 stack에다가 문자를 하나씩 넣어준다.

하지만 조심해야할 부분은 바로 ab bc와 같이 공백이 하나 포함되어있을때이다.

결과적으로는 ba cb처럼 만들어져야하기에 공백기준으로 reversing을 두번 해줘야한다.

따라서 

 

문자열을 돌다가 만약 공백을 만나면 그 전까지의 stack을 pop()하여 sb에 넣는다.

공백이 없다면 그냥 stack에다가 push.

 

 

2. tag가 true일때

이때는 tag내 문자를 다루기에 그냥 sb에다가 append해주면 끝

 

3. 문자 자체가 '<' 일때

 

여기서 생각해야할점은

1번 조건문에서 공백이 있을때 공백 전까지의 문자들을 pop했는데 만약 공백이 없이 <를 만난다면?

abc<abc>이런 경우 cba<abc>가 답으로 나올것이다. 따라서 꺽쇠 전까지 문자들을 pop해주고

tag의 boolean type을 변경해주며 <는 그대로 나와야하기에 sb에 append!

 

4.문자 자체가 '>'일때

닫는 꺾쇠이기에, tag type > false & >도 그대로 나와야하기 sb에 append.

 

**여기서 끝나면 될까?

안됀다. 특수한 경우로 만약 꺾쇠와 공백이 없는 case일 경우 1번 조건문으로 갈텐데 여기선 공백 기준으로 pop을 한다.

만약 공백이 없다면 stack에 값이 남기에, 마지막에 while문을 활용하여 stack을 비워준다면 reversing이 간단히 끝난다.

 

스택을 활용한 문자열 문제에선 while(!stack.isempty) 신경써서 비워주는것도 좋겠다고 느꼈다.

 

import java.io.*;
import java.util.*;

public class Main {
	


	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringBuilder sb = new StringBuilder();
		boolean tag = false;
		Stack<Character> stack = new Stack<Character>();
		for(int i=0; i<str.length(); i++) {
			
			if(str.charAt(i) == '<') {
				//예를들어 문자열이 ab<abc>일때 ab가 아래서 거꾸로 push되고 그 다음 <를 만날때 sb
				//원본 문자열 순서대로 sb에 push되어야 하기 때문이다.
				while(!stack.isEmpty()) {
					sb.append(stack.pop());
				}
				tag = true;
				sb.append(str.charAt(i));
			}
			else if(str.charAt(i) == '>') {
				tag= false;
				sb.append(str.charAt(i));
			}
			
			//tag의 상태에 따라 거꾸로 혹은 정방향으로 문자열을 추가해야함
			else if(tag == true) {
				sb.append(str.charAt(i));
			}
			else if(tag == false) {
				//꺾쇠에 해당되지 않으며 빈칸이 있을 경우 예를들어 ab dc 이런 경우
				if(str.charAt(i) == ' ') {
					while(!stack.isEmpty()) {
						sb.append(stack.pop());
					}
					
					sb.append(' ');
				}
				else {
					stack.push(str.charAt(i));
				}
			}
		}
		
		//만약 공백이없고 꺾쇄도 없는 단어라면 그냥 마지막에 push만해줘도 된다
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		
	
		
		
		
		
		
		System.out.println(sb);
			
		
		
		

	}

}