[프로그래머스] 올바른 괄호

문제

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

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

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

입출력 예

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

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12909#

생각

• 주어진 s에서 ()를 제거해나가면서 마지막에 남는 문자열이 없으면 true

코드

첫 번째 풀이: 정확성 통과, 효율성 통과 X

class Solution {
    boolean solution(String s) {
        if (s.charAt(s.length()-1) == '(' || s.charAt(0) == ')') return false;
        
        String before ="";
        while (s.length() != before.length()){
            before = s;
            s = s.replace("()","");
        }
        
        System.out.println(s);
    
        return s.length() > 0 ? false : true;
    }
}

• while문을 돌며 replace한 뒤 s를 재정의하기 때문에 시간 초과가 발생하였다. 이에 다른 방식을 고민해보았다

두 번째 풀이 (정확성, 효울성 모두 통과!)

class Solution {
    boolean solution(String s) {
        int open = 0;  
        int close = 0; 
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (c == ')') close++;

            if (close > open) return false;
        
        }
        return open == close;
    }
}

• 변수를 재정의할 필요 없이, 주어진 s의 길이 만큼만 반복문을 돌면서 )의 수가 (수보다 많아지면 false 그리고 반복문을 다 돌았을 때 (와 )의 수가 같은지 아닌지에 따라 t/f를 판별하도록 코드를 수정했다 🤗
  

다른 사람의 풀이

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack < Integer > st = new Stack < > ();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(1);
            } else if (s.charAt(i) == ')') {
                if (st.isEmpty()) {
                    answer = false;
                    break;
                } else {
                    st.pop();
                }
            }
        }
        if (!st.isEmpty()) {
            answer = false;
        }
        return answer;
    }
}

• stack을 사용한 풀이를 기록한다
• 들어온 (를 stack에 담아두고 있다가 )가 들어올 때마다 빼내는 (pop) 방식이었다.
• 빼낼 원소가 없거나, 반복이 끝났을 때 남은 (가 있을 경우 false를 return하기에 이해하기 쉽게 짜여진 코드라고 생각했다,<!
• 문제를 보고 사용할 만한 자료구조를 떠올리는 연습을 해야겠다 😚😚