[백준] 17413 단어 뒤집기 2 - 문자열 + 스택JAVA

https://www.acmicpc.net/problem/17413

17413번: 단어 뒤집기 2

코드설명

문자열과 스택 문제이다.

 

문제로직입니다. 

1. '<' 를 만나는경우 tagFlag == true 처리한다. 그리고 지금까지 더해진 stack의 값을 sb에 더해줘야한다. 그리고 '<' 값도 더해준다.
2. tagFlag == true 라면, 만약 '>' 를 만나는경우 tagFlag == false 로 처리한다. 그리고 '>' 값도 더해준다.
3. tagFlag == false 이면서 ' '를 만난다면, 지금까지 더해진 stack의 값을 sb에 더해줘야한다.
4. tagFlag == false 이면서 ' '가 아닌 값이라면, stack에 더한다.

 

문제에서 유의해야할저은, Stack을 활용하여야만 시간초과가 나지 않습니다.

처음에 List를 활용했을경우 LinkedList의 삽입과 삭제는 O(1) 의 시간이지만, 조회에 O(n)의 시간이 걸리기에 시간초과가 납니다.

 

반면에, Stack은 삽입과 삭제가 O(1)이고, 맨위의 값을 조회하는데 또한 O(1)입니다.

 

코드

Stack을 활용하여 시간초과를 해결한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Stack;

public class Main {
	public static int N;
	public static HashMap<String, Integer> hashmap = new HashMap<>();
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static String str;
	public static String[] strSplit = new String[2];
	public static Stack<Character> stack = new Stack<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	str = br.readLine();
    	simulate();
    	System.out.println(sb.toString());
    	
    }
	
	//1. '<' 를 만나는경우 tagFlag == true 처리한다. 그리고 지금까지 더해진 stack의 값을 sb에 더해줘야한다.
	//2. '>' 를 만나는경우 tagFlag == false 로 처리한다. 
	//3. tagFlag == false 이면서 ' '를 만난다면, 지금까지 더해진 stack의 값을 sb에 더해줘야한다.
	//4. tagFlag == false 단
	public static void simulate() {
		boolean tagFlag = false;
		for(int i=0;i<str.length();i++) {
			char temp = str.charAt(i);
			if(temp == '<') {
				tagFlag = true;
				while(!stack.isEmpty()) {
					sb.append(stack.pop());
				}
				sb.append(temp);
			}
			else if(tagFlag == true) { //만약 '<'가 열린 상태라면 이 구간은 아무작업하지않는다.
 				if(temp == '>') { //닫힘처리한다.
 					tagFlag = false;
 				}
 				sb.append(temp);
			}
			else if(tagFlag == false ) { //만약 '< >'태그 안이 아닌 상태에서 빈칸을 만난다면 새로운 작업을 처리한다.
				if(temp == ' ') {
					while(!stack.isEmpty()) {
						sb.append(stack.pop());
					}
					sb.append(temp);
				}
				else {
					stack.add(temp);
				}
			}
		}
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		
	}
	
	
}

 

LinkedList 사용시 시간초과가 난다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Main {
	public static int N;
	public static HashMap<String, Integer> hashmap = new HashMap<>();
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static String str;
	public static String[] strSplit = new String[2];
	public static List<Character> list = new LinkedList<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	str = br.readLine();
    	simulate();
    	System.out.println(sb.toString());
    	
    }
	
	//1. '<' 를 만나는경우 tagFlag == true 처리한다. 그리고 지금까지 더해진 list의 값을 sb에 더해줘야한다.
	//2. '>' 를 만나는경우 tagFlag == false 로 처리한다. 
	//3. tagFlag == false 이면서 ' '를 만난다면, 지금까지 더해진 list의 값을 sb에 더해줘야한다.
	//4. tagFlag == false 단
	public static void simulate() {
		boolean tagFlag = false;
		for(int i=0;i<str.length();i++) {
			char temp = str.charAt(i);
			if(temp == '<') {
				tagFlag = true;
				if(list.size() > 0) {
					for(int j=list.size()-1;j>=0;j--) {
						sb.append(list.get(j));	
					}
					list.clear();
				}
				sb.append(temp);
			}
			else if(tagFlag == true) { //만약 '<'가 열린 상태라면 이 구간은 아무작업하지않는다.
				sb.append(temp);
 				if(temp == '>') { //닫힘처리한다.
 					tagFlag = false;
 				}
			}
			else if(tagFlag == false ) { //만약 '< >'태그 안이 아닌 상태에서 빈칸을 만난다면 새로운 작업을 처리한다.
				if(temp == ' ') {
					for(int j=list.size()-1;j>=0;j--) { //
						sb.append(list.get(j));	
					}
					sb.append(" ");
					list.clear();					
				}
				else {
					list.add(temp);
				}
			}
		}
		
		if(list.size() > 0) {
			for(int j=list.size()-1;j>=0;j--) {
				sb.append(list.get(j));	
			}
			sb.append(" ");
			list.clear();			
		}
	}
	
	
}