mingssssss

1. 문제

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

2. 코드

import java.util.*;

class Solution {
    boolean solution(String s) {

        Stack<Character> stack = new Stack<>();
        
        if (s.charAt(0) == ')') {
            return false;
        }

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

3. 리뷰

올바른 괄호가 쓰였는지 여부이다.

먼저 직관적으로 떠오른 생각은 열린 괄호와 닫힌 괄호의 숫자를 찾아 비교하는 로직이였다.

입력이 10만이여서 O(N)으로 무리 없이 통과할 줄 알았다.

하지만 열린 괄호와 닫힌 괄호의 '짝'이 맞아야 한다.

예를 들어, ( ) ) ( ( ) 의 경우, 열린 괄호와 닫힌 괄호의 짝은 맞지만

올바른 괄호가 아니다.

따라서 열린 괄호를 탐색했을 때, 닫힌 괄호가 있는지 확인을 해야 한다.

먼저 처음 생각한 로직에 구글링을 통해 보완한 내용은,

cnt 변수를 하나 만들어서 열린 괄호일 때 ++, 닫힌 괄호일 때 --를 해준다.

(핵심) cnt가 한 번이라도 0보다 작다면, 닫힌 괄호가 열린 괄호보다 먼저 나온 경우이므로

false를 리턴해준다.

반복문이 끝나고 cnt가 0이 아니라면 짝이 맞지 않는 경우이므로 false를 리턴한다.

cnt가 0보다 작은 경우이면 바로 return false하는 생각이 떠오르지 않았다.

문제를 항상 충분히 읽어보면서 가장 간단한 로직을 구현할 수 있게 연습해야겠다.

두 번째 풀이는 스택을 이용한 풀이이다.

스택은 한 번도 사용해보지 않아서 생소했지만, 구동 방식은 알고있어서 도전해봤다.

먼저 처음 탐색하는 괄호가 닫힌 괄호라면, 바로 false를 리턴해준다.

그게 아니라면, 열린 괄호일 경우 스택에 푸쉬 해주고,

닫힌 괄호일 경우, 스택이 비어있다면 열린 괄호 전에 닫힌 괄호가 나온 경우이므로

false를 리턴해주고, 스택이 비어있지 않으면서 닫힌 괄호가 나왔다면

스택에 들어있는 열린 괄호를 pop해준다.

이런식으로 진행된다면 반복문이 끝났을 때, 스택이 비어있지 않다면

열린 괄호가 닫힌 괄호보다 많은 경우이므로, false를 리턴해준다.

이번 문제를 풀면서 문자열에 대해 더 잘 다룰 수 있게 된 것 같다.

원래 String으로 이어진 문제는 죄다 split("")으로 찢어서

Stirng 배열에 넣어서 풀었는데, 그냥 String문자를 charAt()으로

바로 가져와서 풀면 됐다.(by chogyujin)

앞으로 더 많은 문제를 풀면서 다양한 방법을 생각해봐야겠다.

문제 꼭 10번 이상 읽기!!