[12909] 올바른 괄호

✔ 올바른 괄호

[프로그래머스 12909]

문제 분석하기

'(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 하므로

스택/큐를 사용하여 괄호를 집어 넣은 후, 짝이 맞을 경우 함께 꺼내면서 모든 문자열을 실행한 후 남은 괄호가 있는지 확인함

손으로 풀어보기

1. 스택/큐에 괄호를 집어 넣음
   • 괄호가 짝을 이루는 경우 스택/큐에서 제거
2. 스택/큐의 크기가 0이라면 true, 0이 아니라면 false 반환

슈도코드 작성하기

s('(' 또는 ')'로만 이루어진 문자열)
stack(괄호를 담을 stack)
for(s의 길이만큼) {
    if('('라면) {
        stack에 저장
    }
    if(')'라면) {
        if(stack의 크기가 0이라면) {
            return false;
        }
        stack에서 짝이 맞는 '(' 제거
    }
}
if(stack의 크기가 0이 아니라면) {
    answer = false;
}
return answer;

s('(' 또는 ')'로만 이루어진 문자열)
queue(괄호를 담을 queue)
for(s의 길이만큼) {
    if('('라면) {
        queue에 저장
    }
    if(')'라면) {
        if(queue의 크기가 0이라면) {
            return false;
        }
        queue에서 짝이 맞는 '(' 제거
    }
}
if(queue의 크기가 0이 아니라면) {
    answer = false;
}
return answer;

코드 구현하기

/**
 * 12909) 올바른_괄호
 */
public class K002_12909 {
    // s('(' 또는 ')'로만 이루어진 문자열)
    boolean solution(String s) {
        boolean answer = true;
        // stack(괄호를 담을 stack)
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            // '('라면
            if (s.charAt(i) == '(') {
                // stack에 저장
                stack.add("(");
            }
            // ')'라면
            if (s.charAt(i) == ')') {
                // stack의 크기가 0이라면
                if (stack.size() == 0) {
                    return false;
                }
                // stack에서 짝이 맞는 '(' 제거
                stack.pop();
            }
        }
        // stack의 크기가 0이 아니라면
        if (stack.size() != 0) {
            answer = false;
        }
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K002_12909 solution = new K002_12909();

        String s = "()()";
        boolean result = solution.solution(s);

        System.out.println(result);
    }
}

/**
 * 12909) 올바른_괄호
 */
public class K002_12909 {
    // s('(' 또는 ')'로만 이루어진 문자열)
    boolean solution(String s) {
        boolean answer = true;
        // queue(괄호를 담을 queue)
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            // '('라면
            if (s.charAt(i) == '(') {
                // queue에 저장
                queue.add("(");
            }
            // ')'라면
            if (s.charAt(i) == ')') {
                // queue의 크기가 0이라면
                if (queue.size() == 0) {
                    return false;
                }
                // queue에서 짝이 맞는 '(' 제거
                queue.remove();
            }
        }
        // queue의 크기가 0이 아니라면
        if (queue.size() != 0) {
            answer = false;
        }
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K002_12909 solution = new K002_12909();

        String s = "()()";
        boolean result = solution.solution(s);

        System.out.println(result);
    }
}