[백준 9012번: 괄호](Java)

알고리즘 분류 : Stack (Stack으로도 풀 수 있으나, 해당 게시물에서는 Stack의 속성만을 이용)

 

Stack으로도 풀 수 있는 문제이지만, 올바른 괄호 표현식의 원리를 이용해서 정수 Int type 변수 하나만을 사용했다.

 

[풀이 로직]

1. N을 읽는다

2. N번 String을 받아온다. // "(()))())("

3. 각 케이스마다 새롭게 사용할 index와 input을 초기화 해준다.

    * index의 경우, stack의 top을 가리키는 변수와 동일하게 -1로 설정 해 주었다.

3. 2번에서 받아온 길이만큼 반복문을 돌리며 괄호 하나 하나를 검사한다

4. 정상적인 괄호식의 경우 '('부터 시작하므로, '(' 가 들어오면 index 변수에 +1을 해준다 // stack 에서의 push에 해당

5. ')'가 들어왔다는 것은 무조건 짝 지을 '('가 있어야 한다.

    5-1 index == -1 이면 짝 지을 '('가 없다는 뜻이므로 NO를 출력한다

    5-2 짝 지을 '('가 있다면 index -= 1 // stack에서의 pop에 해당

6. 모든 괄호 검사를 끝낸 이후에, index가 최초상태인 -1이 아니라면 '(' 만 남아있다는 뜻이므로 NO 를 출력하고, 그렇지 않다면 YES를 출력한다

 

NOTE 1. 이중 반복문을 사용하며, inner loop 에서 바로 outer loop의 break 혹은 coninue를 호출하고 싶을 경우 아래와 같이 사용가능하다. (번외) 내가 애정하는 kotlin에서는 outerLoop@ 로 해당 기능을 지원한다

출처 : https://jinn-blog.tistory.com/8

outerLoop :
for (int i = 0 ; i< N; i++){
	for (int j = 1; j< N; j++){
        continue outerLoop;
    }
    // continue outerLoop; 가 실행되면 이부분의 코드는 실행되지 않음
}

 

NOTE 2. BufferedWriter를 사용할 때는 flush()를 호출해주어야 버퍼에 있는 값이 출력된다.

 

---

[정답 코드]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        String input;
        char ps;
        int index;

        outerLoop:
        for (int i = 0; i < N; i++) {
            index = -1;
            input = br.readLine();
            for (int j = 0; j < input.length(); j++) {
                ps = input.charAt(j);
                if (ps == '(') index += 1;
                else {
                    if (index == -1) {
                        bw.write("NO\n");
                        bw.flush();
                        continue outerLoop;
                    } else index -= 1;
                }
            }
            if (index != -1) bw.write("NO\n");
            else bw.write("YES\n");
            bw.flush();
        }
    }
}

 

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

9012번: 괄호