[코딩테스트합격자되기-자바편] 문제08. 올바른 괄호

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

 

출처: 프로그래머스 - 올바른 괄호

 

내용

 

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.
예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 반환고, 올바르지 않은 괄호이면 false를 반환하는 solution() 함수를 완성해 주세요.

 

제약 조건

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

어떤 알고리즘을 적용하려 했나요?

 

스택 구조를 사용해서 문제 풀이 예정입니다.

 

적용 근거는 무엇인가요?

 

'(' 괄호 뒤로는 ')'가 뒤따라와야 하고 '((((()))))' 이렇게 괄호가 연속적으로 나열된 경우 가장 바깥의 '()' 괄호에 들어가야 안의 괄호에 접근할 수 있기에 top-down 구조라고 파악하여 스택 자료 구조로 접근해야 한다고 생각했습니다.

( 좌측괄호 시 +1, 우측괄호 시 -1 적용해서 풀어도 될듯 함)

 

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
13:10	13:30	20분

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

 

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

최대 O(N) 의 시간복잡도를 가져야 하지 않을까..

 

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

s	answer
"()()"	true
"(())()"	true

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(String s) {
    // 1. (괄호를 담을 stack 생성
    for (s) {
        // 2. (괄호 나오면 (괄호 stack 넣기
        // 3. )괄호 나오면 (괄호 stack 에서 찾기, 없으면 false return
    }
    // 4. (괄호 stack이 남아있다면 false return
    return true;
}

 

 

구현

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.add(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

 

 

복기하기

저자 권장 시간	권장 시간 복잡도
30분	O(N)

 

답안과 나의 풀이를 비교해보세요

import java.util.ArrayDeque;

class Solution {
    boolean solution(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();

        char[] a = s.toCharArray();
        for (char c : a) {
            if (c == '(') {
                stack.push(c)
            } else {
                if (stack.isEmpty() || stack.pop() == c) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

 

 

요약하기

• 가장 가까운(최근)이라는 키워드를 보고 스택을 떠올리는 감각이 있어야 한다.
• stack.isEmpty()로 스택이 비어있는지 먼저 체크한 후 pop()한다.
  • EmptyStackException 예외 발생 주의
• push()와 pop()메서드의 시간 복잡도는 O(1) 이다.