#29🤔 올바른 괄호

[문제]

- 아직 안 풀었는데 나만의 우스꽝스러운 생각을 기억에서 지우기 싫어 먼저 글을 저질러버렸다.

출처 : https://school.programmers.co.kr

---

- 문제 조건 자체가 Stack 혹은 Queue를 이용해 풀라고 했다.

- 근데 오늘 길을 걷다 청개구리를 닮은 돌멩이를 봐서 그런지 이상하게 그렇게 풀기가 싫었다.

- 그래서 아래와 같이 변화구를 던져봤다. 개굴

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        // 1. 처음이 ')' or 끝이 '(' 로 끝나면 false 처리
        // 이 경우 배열로 자르고 Stack을 이용하고 자시고 할 필요 없음(리소스 줄이자)
        if(s.charAt(0) == ')' || s.charAt(s.length() - 1) == '(') {
            return false;
        }
        
        // 2. "()()" 같이 이쁜(?) 모양일 경우에도 간단하게 replace 사용
        String afterReplace = s.replace("()", "");
        if(afterReplace.length() == 0) {
            return true;
        }
        
        String[] tmp = afterReplace.split("");
        int left = 0; int right = 0;
        for(String str : tmp) {
            if("(".equals(str)) {
                left += 1;
            } else if(")".equals(str)) {
                right += 1;
            }
        }
        
        if(left == right) {
            return true;
        } else {
            return false;
        }
    }
}

- 근데 역시나 문제는 풀리지 않았다. 근데 또 놀라운건, 대부분의 문제를 통과했다는 것이다.

정확성 테스트에 한 번 더 놀라 자빠졌다.

---

[24.03.06]

- 무친,;; 아래와 같이 하니까 결국 풀림

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        // 1. 처음이 ')' or 끝이 '(' 로 끝나면 false 처리
        // 이 경우 배열로 자르고 Stack을 이용하고 그럴 필요가 없다.(리소스 줄이자)
        if(s.charAt(0) == ')' || s.charAt(s.length() - 1) == '(') {
            return false;
        }
        
        // 2. "()()" 같이 정갈한(?) 모양일 경우에도 간단하게 replace 사용
        String afterReplace = s.replace("()", "");
        if(afterReplace.length() == 0) {
            return true;
        } else {
            // ()))))((((() 같은 경우를 가정하고 한 번더 1번 방법을 사용
            if(afterReplace.charAt(0) == ')' || afterReplace.charAt(afterReplace.length() - 1) == '(') {
                return false;
            }   
        }
        
        String[] tmp = afterReplace.split("");
        int left = 0; int right = 0;
        for(String str : tmp) {
            if("(".equals(str)) {
                left += 1;
            } else if(")".equals(str)) {
                right += 1;
            }
        }
        
        if(left == right) {
            return true;
        } else {
            return false;
        }
    }
}

---

[해답] - 정상적으로 문제 해결 시 업로드 예정

[24.03.06] 정상적으로 풀어봄

- 아래의 글의 정리 부분을 먼저 참고하자

2023.02.02 - [CS/자료구조 및 알고리즘] - #6 Stack(스택) - 개념(FILO : First In Last Out)

#6 Stack(스택) - 개념(FILO : First In Last Out)

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        // 1. 처음이 ')' or 끝이 '(' 로 끝나면 false 처리
        if(s.charAt(0) == ')' || s.charAt(s.length() - 1) == '(') {
            return false;
        }
        
        // 2. "()()" 같이 정갈한(?) 모양일 경우에도 간단하게 replace 사용
        String s_replace = s.replace("()", "");
        if(s_replace.length() == 0) {
            return true;
        }
        
        // 3. 다시 한 번 1번 방법 사용
        if(s_replace.charAt(0) == ')' || s_replace.charAt(s_replace.length() - 1) == '(') {
            return false;
        }

        // 4. Stack 사용
        // 1단계, "(" 만나면 stack에 넣는다. ==> push()
        // 2단계, ")" 만나면 stack에서 가장 최근에 들어온 "("를 꺼내서 지운다. ==> pop()
        // 3단계, 반복문을 다 돌고난 후 stack이 비어있으면 true 아니면 false 반환
        String[] arr = s_replace.split("");
        Stack<String> stack = new Stack<>();
        for(String str : arr) {
            if(")".equals(str) && stack.empty()) {
                return false;
            } else if("(".equals(str)) {
                stack.push(str);    
            } else {
                stack.pop(); // Stack 맨 위 요소 제거
            }
        }       
        
        if(stack.empty()) {
            return true;
        }
        return false;
    }
}

- 위의 코드에서 1~3번 방법은 4번의 stack 방법까지 오기 전에 미리 필터링할 만한 것은 다 걸러줘서 불필요하게 들어가는 리소스를 줄이기 위해 그대로 가져왔다.

- 그리고 무엇보다 1~3번 방법을 주석 처리하고 Stack 방법만 이용하면 아래 같은 사태가 발생한다.

풀이 로직은 맞는데 시간이 많이 들어가서 틀림 처리 되는 것 같다.