올바른 괄호

문제설명

예전에 한번 풀어본 문제였다. 근데 기억이나지않는다. 더군다나 스택/큐 문제인데, 스택/큐가 뭔지는 알지만 어떻게 활용했던건지, 이 문제에서 어떻게 사용해야할지 감이안와서 사용하지 않고 한번 풀어보았다. 조건문,반복문만 사용해서 풀어봤다.

1) 괄호 '(' 와 ')' 의 갯수가 일치하면 true 라는 조건

2) ')' 로 시작하거나 '(' 로 끝나면 무조건 false라는 조건을 넣어서 완성했다.

테스트를 돌려보니 

아버지! 정답을 알려줘!

스터디원들과 얘기를 나누고 지피티한테 물어본 결과
내코드는 좌우 개수는 세지만, 쌍이 안맞는

()))))((((()

이런 경우에도 true를 반환하므로 안되던 것이었다.

지열님의 코드

팀원분이 푸신 코드는 이렇다.

입력받은 String s 를 한글자씩 char로 배열을 만들고, 향상된 for문을 이용해 '('를 넣으면 count 1추가, ')'이면 1빼기 해서 결국 괄호의 짝이 맞으면 count는 0이 되고, 0이 아닌경우(괄호가 짝이 안맞거나, 여는괄호 닫는괄호 갯수가 다르면), false가 된다.

이 코드를 보고 감탄했다. 스터디를 하기 참 잘했다는 생각이 들었다. 이 문제는 스택이나 큐를 사용하지 않고도 잘 된다.

그래서 gpt에게 물어봤는데,

이 문제를 스택으로 푸는 것이 가장 일반적인 방법이며, 시간 복잡도도 O(n)으로 매우 효율적입니다. 하지만 스택 이외에도 다른 방법으로도 풀 수 있습니다. 예를 들어, 문자열을 처음부터 끝까지 순회하면서 '(' 문자와 ')' 문자의 개수를 각각 세어서 개수가 같은지 확인할 수도 있습니다. 이 방법의 시간 복잡도도 O(n)입니다. 하지만 스택을 이용한 방법이 가장 직관적이고 이해하기 쉬우며, 스택을 이용한 다른 문제들도 많이 출제되므로, 스택으로 푸는 것이 좋습니다.

라고 했다. 출제자의 의도대로 푸는게 맞긴하겠지..?

 

아무래도 스택/큐 카테고리의 문제니  스택이나 큐를 사용해서 풀어보면

class Solution {
    public boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c); // '('를 스택에 쌓습니다.
            } else if (stack.isEmpty()) {
                // 스택이 비어있는데 ')'를 만나면 올바른 괄호 문자열이 아닙니다.
                return false;
            } else {
                stack.pop(); // 스택에서 ')'를 제거합니다.
            }
        }
        
        // 문자열을 모두 처리했는데 스택에 여전히 '(' 문자가 남아있다면 올바른 괄호 문자열이 아닙니다.
        return stack.isEmpty();
    }
}

이런식으로 풀면 된다.

이것도 어찌보면 우리팀원분이 푼 코드를 스택으로 풀면 이렇게 된다.

 

스택/큐 다시 공부해야겠다.