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

문제 설명

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

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

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

문제 설명

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

입출력 예

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

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

()의 짝을 찾아 모든 괄호가 닫혀있으면 true를, 아니라면 false를 반환하는 문제이다.

 

1. 문제풀이

괄호의 짝을 찾아야 하므로, '('문자를 찾아와서 뒤의 문자 중 ')' 문자가 존재하는지 확인하는 방식으로 접근하였다.

이중 for문을 사용하였고, start, end 변수를 선언하여 짝이 지어진 '(', ')' 문자는 검사하지 않도록 제외하였다.

효율성을 위해  StringBuilder객체를 선언하여 sb 변수에 짝이 지어진 괄호는 공백으로 치환하게끔 하여

for문 다 돌고 나온 sb 문자에 공백이 아닌 값이 존재한다면 false값을 반환하도록 하였다.

 

2. 코드

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        StringBuilder sb = new StringBuilder(s); //효율성을 위해 StringBuilder로 선언
        int start = 0; //시작기준 인덱스
        int end = 0; //끝기준 인덱스
        
        //s 길이만큼 반복
        for(int i=0;i<s.length(); i++){
            char now = s.charAt(i); //문자하나씩 자름
            start = i;
            
            if(now=='('){
                start = i;
                //끝기준 인덱스 다음 문자부터 검사
                for(int j=end+1; j<s.length();j++){
                    char match = s.charAt(j);
                    //닫힌괄호면서, ')'의 순서가 찾은'('보다 뒤에 있는 경우
                    if(match==')'&& start<j){
                        sb.setCharAt(j,' ');//sb의 인덱스를 공백으로 치환
                        sb.setCharAt(start,' ');
                        end = j;//')'를 짝으로 사용했으므로 끝 인덱스 변경해줌
                        break;
                    }
                }
            }
        }
        
        //sb에 공백이 아닌값이 존재하면 짝없는 괄호가 존재하는것 이므로 false를 리턴
        for(int i=0;i<sb.length();i++){
            char now = sb.charAt(i);
            if(now!=' '){
                return false;
            }
        }

        return true;
    }
}

처음에 substring 함수를 사용하여 now, match 변수를 잘랐는데, 효율성 검사에서 통과하지 못하였다.

따라서 효율성을 높이기 위해 char 변수로 비교하도록 charAt 함수를 사용하고, now, match 변수 또한

char타입으로 선언해 주었다.

위와 같이 변경하니 효율성 테스트에도 통과하였다.

 

하지만, 위의 문제를 Stack구조를 사용하면

더 간단하게 풀 수 있다는 사실을 검색을 통해 알게되었다.

아래는 Stack 구조를 이용한 코드이다.

 

3. 개선된 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            //여는 괄호일 때
            if(c == '('){
                stack.push(c);
            }
            
            //닫는 괄호일 때
            if(c == ')'){
                if(stack.size() == 0){
                    return false;
                }
                else stack.pop();
            }
        }
        if(stack.size() != 0) answer = false;

        return answer;
    }
}

출처 : https://hyojun.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%98%AC%EB%B0%94%EB%A5%B8-%EA%B4%84%ED%98%B8-Java