[프로그래머스] 올바른 괄호 - 자바(Java)

문제 링크

프로그래머스

 

문제 설명

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

"()()" 또는 "(())()" 는 올바른 괄호입니다. 

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

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

제한사항

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

입출력 예

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

 

첫번째 문제 풀이

* 혼자 풀어본 후 다른 코드를 보고나서 개선된 문제풀이를 하나 더 작성했다.

괄호 문자열(s)를 한 문자씩 확인하면서 다음 문자랑 괄호 조합이 되는지 확인해야한다.

괄호를 Stack에 쌓으면서 이전 문자와 다음 문자의 조합이 괄호가 되는지 알 수 있다.

원본 문자열의 문자를 저장할 Stack과 괄호 조합이 안되는 경우 저장할 Stack을 두 개 선언하여 구현했다.

 

[고려사항]

괄호 문자열(s)는 최대 100,000(10만)개 이하이므로 문자열 조작에 대한 시간 복잡도를 고려해야한다.

시간을 최소화할 수 있는 방법으로 Stack을 생각했다.

Stack의 삽입, 삭제, isEmpty, peek 연산은 모두 O(1)의 시간 복잡도를 가지고, 필요한 연산은 저 4가지면 되기 때문이다.

 

그래서 내가 구현한 방식에서는

    1) Stack에 문자열을 문자로 변환하여 삽입 : O(N)

    2) Stack을 순회하면서 Stack 연산 : O(N)이라서

전체 시간 복잡도는 O(N)이 된다.

 

[풀이 과정]

1. 문자열을 문자(char)로 변환해서 원본 Stack에 할당한다. 
   • String에서 char로 형변환을 하기 위해 charAt()을 이용한다.
2. 괄호 완성이 안되는 경우, 원본 Stack의 char값을 저장할 Stack을 선언
3. 아래 과정을 원본 Stack이 빌 때 까지 반복한다.
4. 원본 Stack에서 pop()한 값을, 저장 Stack에 값이 있는 경우에 괄호 완성이 되는지 확인한다.
   • 괄호가 완성되면 저장 Stack에서 해당 값을 pop(); ➔ 괄호 삭제
   • 괄호가 완성되지 않으면 저장 Stack에 해당 값을 push();
5. 반복문이 끝난 후, 저장 Stack에 값이 남아있다면 올바른 괄호가 아니다.
   • 괄호가 완성되어서 값이 pop(), 즉 삭제되었다면 저장 Stack은 비어있어야한다.

첫번째 코드

import java.util.*;
class Solution {
	public boolean solution(String s) {
        Stack<Character> stackInitial = new Stack<>(); // 문자열을 문자로 분할해서 넣을 Stack
        for (int i=0; i<s.length(); i++) {
            stackInitial.push(s.charAt(i));
        }

        char c;
        Stack<Character> stackStorage = new Stack<>(); // 괄호 완성이 안되는 경우 초기 Stack의 char 값을 저장할 Stack
        while (!stackInitial.isEmpty()) {
            c = stackInitial.pop();
            if (!stackStorage.isEmpty()) {
                char charStorage = stackStorage.peek();
                if (c == '(' && charStorage == ')') { // 괄호 완성하면 다음 문자로 넘어감
                    stackStorage.pop();
                    continue;
                }
            }
            stackStorage.push(c);
        }

        // 남은 문자열이 있으면 실패
        if (!stackStorage.isEmpty()) return false;
        else return true;
    }
}

 

두번째 문제 풀이

다른 사람들의 풀이를 보니까, 완성되지 않은 괄호를 굳이 Stack에 넣지 않고 열린 괄호와 닫힌 괄호의 개수로 확인하는 방법도 있다.

열린 괄호인 경우엔 변수를 증가시키고, 닫힌 괄호인 경우엔 변수를 감소시키면서 연산하고,

마지막에 변수가 0인 경우에만 올바른 괄호라고 판단하면 된다.

 

실행 시간을 비교해보면 Stack을 이용한 첫번째 코드보다 훨씬 개선된 것을 확인할 수 있었다.

Stack을 사용한 1번째 코드 vs 개선한 코드

 

Stack을 사용한 1번째 코드 vs 개선한 코드

 두번째 코드

class Solution {
    boolean solution(String s) {
        
        int cnt = 0;
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') { // 열린 괄호일때
                cnt++;
            } else {
                if (cnt == 0) return false; // 닫힌 괄호일때 cnt가 0이면 열린 괄호가 없는것이므로 올바른 괄호 아님
                else cnt--;
            };
        }
        if (cnt == 0) return true;
        else return false;
        
    }
}