(알고리즘 스터디) 3주차 금 _ 스택&큐📦 _ (Programmers) 올바른 괄호

🌟 프로그래머스 / 스택&큐 / Level2 / 올바른 괄호

📃 문제

프로그래머스

🚫 제한 사항

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

👀 입출력 예

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

🤔 풀이 방법

1️⃣ 단순 배열을 통한 풀이 (1)

➡️ 문자열 s 를 나누어 배열을 만들고 "(" 를 +1 로 하고 ")" 를 -1 로 했을 때, 앞에서부터 탐색했을 때 그 합이 0보다 작아지거나 최종 합이 0이 아니면 정상적인 괄호의 형태라고 볼 수 없다.

class Solution {
    boolean solution(String s) {
        int total = 0;
        
        // 문자열 분해
        String[] str = s.split("");
        
        // 배열 전체 탐색
        for (int i=0; i<str.length; i++) {
            if (total < 0) { // 탐색 중 음수가 되면 false
                return false;
            }
            
            String tmp = str[i];
            
            if (tmp.equals("(")) {
                total++;
                continue;
            }
            total--;
        }
        
        // 전체를 탐색했을 때 합이 0이 아니면 false
        if (total == 0) {
            return true;
        }
        
        return false;
    }
}

➡️ 실행결과 효율성 테스트를 통과하지 못했다.

2️⃣ Stack 을 이용한 풀이 (1)

➡️ 아래와 같은 과정으로 움직인다.

["(", "(", ")", ")", "(", ")"] 의 상태로 문자열을 쪼갠 뒤

① Stack 이 비어있는지 확인
① -1 _ 비어있는 경우 : 스택에 바로 넣는다 (push)
① -2 _ 비어있지 않은 경우 : ② 로 넘어감

② peek 을 통해 맨 위 요소를 꺼내고 원소와 합침
② -1 _ 합쳤을 때 () 가 되는 경우 : 스택에서 맨 위를 뺸다 (pop)
② -2 _ 합쳤을 때 () 가 되지 않는 경우 : 스택에 넣는다 (push)

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<String> box = new Stack<>();
        
        String[] str = s.split("");
        
        for (String ss : str) {
            if (box.isEmpty()) {
                box.push(ss);
                
                continue;
            }
            
            String match = box.peek() + ss;
            
            if (match.equals("()")) {
                box.pop();
                continue;
            }
            
            box.push(ss);
        }
        
        if (box.isEmpty()) {
            return true;
        }
        
        return false;
    }
}

➡️ 똑같이 효율성 테스틑 통과하지 못했다. 그리고 일반 테스트도 배열을 이용한 풀이보다는 오래걸렸다.

❓빠르게 작동하지 못하는 이유

① 반복문 ➡️ 하지만 전체 탐색을 해야 잘못된 것을 알 수 있으므로 줄이기 어렵다.

② 문자열 ➡️ 문자열의 경우 연산 또는 비교가 숫자보다 오래걸린다. 괄호 문자 대신 숫자로 연산할 수 있는 방법을 생각해보자.

3️⃣ Stack 을 이용한 풀이 (2)

➡️ 아무래도 문자열을 만들고 비교하는 과정에서 시간이 걸릴 것 같다. 해당 부분을 숫자값으로 대신해서 계산해본다.

int sum = '(' - ')'; //  결과 : -1

이렇게 두 차를 확인하고 equals 를 통한 문자열 비교대신 sum 과 일치하는지 확인함으로써 속도를 개선한다.

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        // 모두 char 형태로 바꿔준다.
        Stack<Character> box = new Stack<>();
        char[] c = s.toCharArray();
        int sum = '('-')'; // -1

        for (char ss : c) {
            if (box.isEmpty()) {
                box.push(ss);

                continue;
            }

            if (sum == box.peek()-ss) {
                box.pop();
                continue;
            }

            box.push(ss);
        }
        
        if (box.isEmpty()) {
            return true;
        }
        
        return false;
    }
}

➡️ 이번에는 효율성 테스트 2개중에 1개를 성공했다.

4️⃣ 단순 배열을 통한 풀이 (2)

➡️ 맨 처음 풀이 때도 스택보다는 배열이 처리 속도가 빨랐으니 똑같은 원리를 첫번째 풀이에 적용시켜 보았다.

class Solution {
    boolean solution(String s) {
        int total = 0;
        
        int left = '(';
        
        char[] str = s.toCharArray();
        
        for (int i=0; i<str.length; i++) {
            if (total < 0) {
                return false;
            }
            
            if (str[i] == left) {
                total++;
                continue;
            }
            total--;
        }
        
        if (total == 0) {
            return true;
        }
        
        return false;
    }
}

➡️ 문제의 주제인 Stack 으로 푼건 아니지만 효율성 테스트를 모두 통과하였다.

💻 풀이 코드

[level 2] Title: 올바른 괄호, Time: 4.74 ms, Memory: 52.8 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@3fafcc5