[Ch.05 - StackQueue] 01. 올바른 괄호

1. 올바른 괄호

 

설명

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

입력

첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

출력

첫 번째 줄에 YES, NO를 출력한다.

예시 입력 1 

(()(()))(()

예시 출력 1

NO

---

import java.util.Scanner;
import java.util.Stack;

//올바른 괄호
//isEmpty로 확인
//push, peek,pop
public class Main {
	public String solution(String str) {
		String answer = "YES";
		Stack<Character> stack = new Stack<>();
		for (char x : str.toCharArray()) {
			stack.push(x);
		}
		int cnt = 0;
		while (!stack.isEmpty()) {
			if (stack.pop() == ')') {
				if (stack.isEmpty())
					return answer = "NO";
				while (stack.pop() != '(') {
					cnt++;
				}

				while (cnt != 0) {
					stack.push(')');
					cnt--;
				}
			} else
				answer = "NO";
		}

		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str = kb.next();
		System.out.println(T.solution(str));
	}

}

-> 넣고 나서 확인하는 방법, Runtime Error 발생하는 테스트케이스 존재

 

import java.util.*;

public class Main {
	public String solution(String str) {
		char[] arr = str.toCharArray();
		Stack<Character> stack = new Stack<>();
		String answer = "NO";

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == '(')
				stack.push(arr[i]);
			else if (arr[i] == ')' && !stack.isEmpty())
				stack.pop();
			else if (arr[i] == ')' && stack.isEmpty())
				return answer;
		}
		if (stack.isEmpty()) {
			return answer = "YES";
		} else
			return answer;

	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str = kb.next();
		System.out.println(T.solution(str));
	}
}

---

1. Stack 이용

2. cnt 이용

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str= in.next();
    System.out.println(Solution(str));
  }
  private static String Solution(String str){
    Stack<Character> stack = new Stack<>();
    for(char c:str.toCharArray()){
      if(stack.isEmpty()){
        if(c==')') return "NO";
        else stack.push(c);
      }
      else if(!stack.isEmpty()){
        if(stack.peek()=='(' && c==')')
          stack.pop();
        else stack.push(c);
      }
    }
    
    return stack.isEmpty()?"YES":"NO";
  }
}

 

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str= in.next();
    System.out.println(Solution(str));
  }
  private static String Solution(String str){
    int cnt=0;
    for(char c:str.toCharArray()){
      if(c==')'){
        cnt--;
      }
      else if(c=='('){
        cnt++;
      }
      if(cnt<0){
        return "NO";
      }
    }
    return cnt==0?"YES":"NO";
  }
}

---

+) 03.03

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str = in.next();
    Main main = new Main();
    System.out.println(main.solution(str));
  }
  public String solution(String str){
    String answer="YES";
    Stack<Character> stack = new Stack<>();
    
    for(char c:str.toCharArray()){
      if(c==')'&&!stack.isEmpty() && stack.peek()=='(') stack.pop();
      else stack.push(c);
    }
    if(!stack.isEmpty()) return answer="NO";
    
    return answer;
  }
}