Baekjoon 9012 괄호 - Stack

 

더 깔끔한 노션을 원한다면

Baekjoon 9012 괄호 - Stack

9012번: 괄호

Stack

라이브 코딩에서 나올법한 문제이므로 다시 풀어보았다.

괄호가 올바른 괄호인지 확인하는 함수 : isVPS

private boolean isVPS(char[] PS, Stack<Character> stack) {
  for (int i = 0; i < PS.length; i++) {
    char ch = PS[i];
    if (ch == ')') {
      if (stack.isEmpty()) {
        return false;
      } else {
        stack.pop();
      }
    } else {
      stack.push('(');
    }
  }
  if (!stack.isEmpty()) {
    return false;
  }
  return true;
}

'(' 일 때에는 stack에 push해준다.

')' 일 때에는 stack이 비어있는지 확인한다.

• stack 비어있다면 false를 리턴한다.

괄호 문자열이 끝났는데 stack이 비어있지 않다면 false를 리턴한다.

isRange 함수는 x, y값이 배열 범위에 벗어나는지 체크해준다.

방문했는지(visit), 같은 단지인지(map)를 확인해준 뒤, 재귀(DFS)를 돌려준다.

전체 코드

/**
 * @포인트 Stack 문제
 * @포인트 Stack은 '('만 넣고 ')'가 나올 때에는 pop만 해준다.
 * @포인트 stack이 비어있는지 확인해줘야 한다(isEmpty).
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    Baekjoon solution = new Baekjoon();
    solution.P9012();
  }
}

class Baekjoon {
  public void P9012() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // StringTokenizer st = new StringTokenizer(br.readLine());
    Stack<Character> stack;
    int N = Integer.parseInt(br.readLine());
    for (int i = 0; i < N; i++) {
      stack = new Stack<>();
      char[] PS = br.readLine().toCharArray();
      if (isVPS(PS, stack)) {
        System.out.println("YES");
      } else {
        System.out.println("NO");
      }
    }
  }

  private boolean isVPS(char[] PS, Stack<Character> stack) {
    for (int i = 0; i < PS.length; i++) {
      char ch = PS[i];
      if (ch == ')') {
        if (stack.isEmpty()) {
          return false;
        } else {
          stack.pop();
        }
      } else {
        stack.push('(');
      }

    }
    if (!stack.isEmpty()) {
      return false;
    }
    return true;
  }
}