[1218] 괄호 짝짓기

✔ 괄호 짝짓기

[SWEA 1218]

문제 분석하기

스택을 이용해 괄호를 집어 넣은 후, 짝이 맞을 경우 함께 꺼냄

모든 문자열을 실행한 후 남은 괄호가 있을 경우 짝을 찾을 수 없어 유효하지 않음

손으로 풀어보기

1. 스택에 괄호를 집어 넣음
   • 괄호가 짝을 이루는 경우 스택에서 함께 제거
2. 스택의 크기가 0이라면 유효하므로 1 반환, 0이 아니라면 유효하지 않으므로 0 반환

슈도코드 작성하기

T(테스트 케이스 수) = 10
for(T만큼) {
    n(테스트케이스의 길이)
    s(문자열)
    answer(문자열이 유효한지 유무) = 0
    stack(괄호를 담을 stack)
    for(i -> n만큼) {
        ch(문자열[i])
        if(ch가 ')'이면서 stack.peek가 '('라면) {
            stack.pop
        }
        else if(ch가 ']'이면서 stack.peek가 '['라면) {
            stack.pop
        }
        else if(ch가 '}'이면서 stack.peek가 '{'라면) {
            stack.pop
        }
        else if(ch가 '>'이면서 stack.peek가 '<'라면) {
            stack.pop
        }
        else {
            stack.push
        }
    }
    if(stack의 크기가 0이라면) {
        answer = 1
    }
    #T와 answer 반환
}

코드 구현하기

/**
 * 1218) 괄호_짝짓기
 */
public class D002_1218 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스 수) = 10
        int T = 10;
        // T만큼
        for (int test_case = 1; test_case <= T; test_case++) {
            // n(테스트케이스의 길이)
            int n = sc.nextInt();
            // s(문자열)
            String s = sc.next();
            // answer(문자열이 유효한지 유무)
            int answer = 0;
            // stack(괄호를 담을 stack)
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < n; i++) {
                // ch(문자열[i])
                char ch = s.charAt(i);
                // ch가 ')'이면서 stack.peek가 '('라면
                if (ch == ')' && stack.peek() == '(') {
                    stack.pop();
                }
                // ch가 ']'이면서 stack.peek가 '['라면
                else if (ch == ']' && stack.peek() == '[') {
                    stack.pop();
                }
                // ch가 '}'이면서 stack.peek가 '{'라면
                else if (ch == '}' && stack.peek() == '{') {
                    stack.pop();
                }
                // ch가 '>'이면서 stack.peek가 '<'라면
                else if (ch == '>' && stack.peek() == '<') {
                    stack.pop();
                }
                // ch가 '(', '[', '{', '<'라면
                else {
                    stack.push(ch);
                }
            }
            // stack의 크기가 0이라면
            if (stack.size() == 0) {
                answer = 1;
            }
            // #T와 answer 반환
            System.out.println("#" + test_case + " " + answer);
        }
    }
}