[24/11/05] 스택

1406

감도 안잡혀서 빠르게 답 봤다.

처음엔 List로 대충 구현하면 될거같은데 싶었다가 시간제한 보니 자바는 2초길래 명령어 개수가 최대 500,000개이면 O(NlogN)에서 무조건 끊어야되는데 싶었다. 그럴려면 List로 하는 순간 ArrayList는 삽입하는 순간 뒷 데이터 전부 밀어야해서 O(N), LinkedList는 찾는 과정에서 O(N)이라 이것을 각각 반복하면 O(N^2) 으로 타임아웃이 불 보듯 뻔했다.

 

커서고 뭐고 일단 처음 들어간게 가장 먼저 나오길래 큐인가 싶었는데 그러면 커서부분을 어떻게 해야되지? 큐  중간에 넣어야하는데? 에서 문제가 발생했다. 

 

큐 중간에 넣어버릴수가 없으니 (스택도 마찬가지고) 커서 있는걸 기준으로 서로 다르게 쪼갰어야 했다. 쪼개기만 하면 큐로는 구현이 안되고 스택으로 될거같다는것을 알 수 있다.

 

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        Stack<Character> leftStack = new Stack<>();
        Stack<Character> rightStack = new Stack<>();

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        for(int i=0; i<str.length(); i++){
            leftStack.push(str.charAt(i));
        }
        
        int n = Integer.parseInt(bf.readLine());
        for(int i=0; i<n; i++){
            String input = bf.readLine();
            switch (input.charAt(0)) {
                case 'L':
                    if(leftStack.isEmpty()){
                        break;
                    }
                    rightStack.push(leftStack.pop());
                    break;
                case 'D':
                    if(rightStack.isEmpty()){
                        break;
                    }
                    leftStack.push(rightStack.pop());
                    break;
                case 'B':
                    if(leftStack.isEmpty()){
                        break;
                    }
                    leftStack.pop();
                    break;
                case 'P':
                    leftStack.push(input.charAt(2));
                    break;
            }
        }
        while(!leftStack.isEmpty()){
            rightStack.push(leftStack.pop());
        }
        while(!rightStack.isEmpty()){
            sb.append(rightStack.pop());
        }
        System.out.println(sb.toString());
        
    }
}

 

참고: 

https://dksek3050.tistory.com/36

[백준 Java] 1406번 에디터 (스택)

https://ittrue.tistory.com/106

[Java] 자바 StringBuilder와 StringBuffer 정리 및 사용법

----------------------------------------------------------------------- -----------------------------------------------------------------------

9012

어려운 문제는 아니었지만 구현에 좀 시간을 썼다.

기본적으로 ')' 가 오는 순간 가장 최신의 '('가 있는지 확인하고 있다면 이걸 뽑으면 되는거고 없다면 VPS가 안되는 문자열이다. 따라서 "가장 최신의 ("를 보고 Stack 쓰면 될거같은데 싶었다.

 

실패하는 조건은 총 2개로

)의 개수 < ( 개수 

)의 개수 > ( 개수 이다.

 첫번째 경우는 VPS flag가 true이지만 실제로 VPS문자열은 아닌 경우가 있다. 이를 좀 처리 해줘야한다.

두번째 경우는 마찬가지로 VPS flag가 모두 false로 걸릴것이다.

 

 

//내 풀이
import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        for(int i=0; i<n; i++){
            String str = bf.readLine();
            boolean VPS = true;
            Stack<Character> stack = new Stack<>();
            for(int j=0; j<str.length(); j++){
                char c= str.charAt(j);
                if(stack.push(c)==')'){
                    stack.pop(); //')' pop
                    if(!stack.isEmpty() && stack.peek()=='(' ){
                        stack.pop(); //'(' pop
                    }
                    else{
                        VPS = false;
                        break;
                    }
                }
                
            }
            if(VPS==true && stack.isEmpty()){
                System.out.printf("YES\n");
            }
            else{
                System.out.printf("NO\n");
            }
        }
        
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			sb.append(solve(br.readLine())).append('\n');
		}
		
		System.out.println(sb);
	}
 
	public static String solve(String s) {
 
		Stack<Character> stack = new Stack<>();
 
		for (int i = 0; i < s.length(); i++) {
 
			char c = s.charAt(i);
 
			// 여는 괄호일 경우 스택에 넣는다.
			if (c == '(') {
				stack.push(c);
			}
 
			// 아래는 모두 닫는 괄호 일 경우들이다.
 
			// 스택이 비어있는 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
			else if (stack.empty()) {
				return "NO";
			}
			// 그 외의 경우 stack 원소를 pop 한다.
			else {
				stack.pop();
			}
		}
 
		/*
		 * 모든 검사 마치고 스택에 잔여 요소가 있으면 여는 괄호가 많은 경우는 "NO" 
		 * 스택이 비어있으면 온전한 수식이므로 "YES" 이다.
		 */
 
		if (stack.empty()) {
			return "YES";
		} 
		else {
			return "NO";
		}
	}
}

위는 참고풀이인데 나처럼 한 Statement에서 isEmpty()와 (인지를 판단하지 않고 따로 판단하는 차이만 있다.