올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java

프로그래머스

 

문제 설명

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

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

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

제한사항

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

---

입출력 예

s answer

"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

 

---

• 문제를 분석해보면, 닫힌 괄호가 임의 위치의 열린 괄호와 상쇄되는 것이 아니라, 닫힌 괄호가 나오기 바로 전의, 즉 가장 가까운(최근)열린 괄호와 상쇄된다는 점을 발견해야 한다.
• 가장 가까운(최근) 이라는 키워드를 보고 '스택'을 떠올리는 감각을 가져야 한다.

1. 문자열을 앞에서 하나씩 보면서 열린 괄호'('가 나오면 푸시
2. 닫힌 괄호')'가 나오면 pop 연산을 통해 문자열에서 열린 괄호, 닫힌 괄호 한 쌍을 상쇄한다.
3. 1-2번을 반복하여 스택에 열린 괄호가 남아있다면 짝이 맞지 않는 것이고, 짝이 남아 있지 않다면 짝이 맞는 것으로 판단하면 된다.

---

1차 도전

// Stack 풀이
// 1. '(' 열린 괄호일 경우 push
// 2. ')' 닫힌 괄호일 경우 pop
// 3. 스택에 괄호가 남아있으면 false / 남아있지 않으면 true

import java.util.*;

class Solution {
    boolean solution(String s) {
        // return
        boolean answer = true;

        // deque 객체 생성
        ArrayDeque<Character> stack = new ArrayDeque<>();
        
        // s 문자열의 각 요소를 char 배열에 담기
        char[] a = s.toCharArray();
        
        for(char c : a){
            // 열린 괄호일 경우 push
            if(c == '('){
                stack.push(c);
            } else {
            // 닫힌 괄호일 경우 pop
                if(stack.pop() == c){
                    return false;
                }
            }
        }
        
        System.out.println(Arrays.toString(a));
        System.out.println(stack);

        return answer;
    }
}

• NoSuchElementException 예외 발생
  • 스택이 비어있을 때 pop()을 호출했기 때문에 발생
  • 따라서 pop()을 하기 전에 스택이 비어있는지 체크해야 함!!!!

2차 도전

// Stack 풀이
// 1. '(' 열린 괄호일 경우 push
// 2. ')' 닫힌 괄호일 경우 pop
// 3. 스택에 괄호가 남아있으면 false / 남아있지 않으면 true

import java.util.*;

class Solution {
    boolean solution(String s) {

        boolean answer = true;
        
        // deque 객체 생성
        ArrayDeque<Character> stack = new ArrayDeque<>();
        
        // s 문자열의 각 요소를 char 배열에 담기
        char[] a = s.toCharArray();
        
        for(char c : a){
            // 열린 괄호일 경우 push
            if(c == '('){
                stack.push(c);
            } else {
            // 스택이 비어있다면 바로 false return, 닫힌 괄호일 경우 pop
                if(stack.isEmpty()){
                    return false;
                } else {
                    stack.pop();
                }
            }
        }

        return stack.isEmpty();
    }
}

 

1. deque 객체를 생성했다.
2. 문자열의 각 문자를 char형 배열에 담아서 하나씩 스택에 넣을 준비 완료
3. for문을 사용하여 배열 요소 꺼내서 비교하기
3-1. 요소가 '(' 열린 괄호일 경우 스택에 push
3-2. (3-1번이 거짓인 경우)
    '(' 닫힌 괄호라는 의미이기 때문에, pop으로 열린 괄호를 빼준다.
    3-2-1.
     단, 이때 스택 안에 열린 괄호가 없다면 ( = 스택이 비어있다면) pop할 요소가 없기 때문에(예외 발생함) 바로 false를 리턴해         야  한다. 따라서 스택이 비어있는지 여부부터 우선 확인한다. 비어있다면 바로 false 리턴,
     3-2-1이 거짓이라면, stack에서 pop 진행
4. for문을 모두 돌고 나서 스택에 요소가 남아있으면, 짝이 안맞다는 의미이므로 false/ 요소가 비어있다면 짝이 맞다는 의미이므로 true를 리턴해야 한다. 이때, isEmpty()로 바로 결과를 return 해준다.