백준 17413: 단어 뒤집기 2(java)
문제
풀이
입력받은 문자열을 뒤집어야 하므로 스택을 이용해 풀이한다. 스택은 후입선출(FIFO) 구조이므로 먼저 입력되어 먼저 삽입된 값이 나중에 출력된다.
for문과 charAt() 메소드를 이용해 한 문자씩 처리할 것이므로 Character가 삽입되는 스택을 선언하고, StringBuilder를 사용해 한 번에 출력한다. 이때 처리할 문자 ch의 위치에 따라 처리 방식을 다르게 해야 한다.
- ch가 괄호 바깥에 있는 경우: < > 바깥의 값은 뒤집어야 하므로 append하기 전에 스택을 거쳐야 한다.
- ch가 괄호 안에 있는 경우: < > 안의 값은 그대로 출력해야 하므로 바로 append한다.
boolean flag=true; //true면 뒤집고 false면 그대로1, 2번 케이스 중 어떤 방식으로 처리할지 결정하기 위해 boolean 타입 flag 변수를 선언했다. flag가 true이면 1번, false이면 2번 케이스이다.
flag=true일 때는 아래와 같이 처리한다. 이때 sb는 StringBuilder 객체이다.
if(flag) { //flag=true
if(ch!=' ') //공백 아닐 때
stack.push(ch);
else { //공백일 때
while(!stack.isEmpty())
sb.append(stack.pop());
sb.append(' ');
continue;
}
}ch가 괄호 바깥에 있어 스택을 이용해 한 번 뒤집은 후 출력해야 한다. 입력된 문자열은 공백을 기준으로 분리되므로 ch가 공백일 때와 아닐 때를 다시 구분해야 한다. ch가 공백일 때는 새로운 단어를 처리하기 전에 이전 단어를(뒤집은 단어) 출력해야 하며, while문을 사용해 스택이 공백 상태가 될 때까지 스택의 요소들을 모두 pop한다. 마지막에 공백을 추가해야 함에 주의하자.
flag=false일 때는 문자열을 뒤집지 않으므로 스택을 거치지 않고 바로 append한다.
else { //flag=false
sb.append(ch);
}
위 과정을 위해 flag 값을 적절히 설정해야 하는데, 문자열을 뒤집을지 여부는 괄호를 기준으로 달라지므로 if-else문을 사용해 반복을 진행하다 괄호를 만나면 flag를 변경한다.
ch가 '<'일 경우 '>'가 등장할 때까지 뒤집지 않고 출력하므로 flag를 false로 변경하고, ch를 바로 StringBuilder에 append한다.
if(ch=='<') {
while(!stack.isEmpty()) {
sb.append(stack.pop());
}
flag=false;
}'<' 이전에 이미 입력된 알파벳이 있을 경우 이들을 먼저 출력한 뒤 괄호가 시작되어야 하므로 스택이 공백 상태가 될 때까지 모두 pop한다.
ch가 '>'일 경우 괄호가 끝났으므로 flag를 true로 변경한다.
else if(ch=='>') {
flag=true;
sb.append(ch);
}이때 괄호까지 append함에 주의해야 한다.
마지막 반복일 때 스택이 공백 상태가 아니라면 남은 요소들을 모두 append한다.
if(i==s.length()-1) {
while(!stack.isEmpty())
sb.append(stack.pop());
}
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Stack<Character> stack=new Stack<>();
StringBuilder sb=new StringBuilder();
String s=br.readLine();
boolean flag=true;
for(int i=0; i<s.length(); i++) {
char ch=s.charAt(i);
if(ch=='<') {
while(!stack.isEmpty()) {
sb.append(stack.pop());
}
flag=false;
}
else if(ch=='>') {
flag=true;
sb.append(ch);
continue;
}
if(flag) {
if(ch!=' ')
stack.push(ch);
else {
while(!stack.isEmpty())
sb.append(stack.pop());
sb.append(' ');
continue;
}
}
else
sb.append(ch);
if(i==s.length()-1) {
while(!stack.isEmpty())
sb.append(stack.pop());
}
}
System.out.println(sb);
}
}