[고득점 kit][스택][lv.2] 올바른 괄호 - 자바(Java)

 

프로그래머스 > 코딩테스트 연습 > 코딩테스트 고득점 kit > 스택/큐 > 올바른 괄호 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

 

 

 

---

 

문제

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

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

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

제한사항

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

 

 

✅ 풀이 과정

0.  자료구조 / 알고리즘 선택

스택의 대표적인 문제! 

 

1. 복잡도 고려

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

문자열이 100,000이하의 자연수이다. 

나는 Stack 컬렉션을 사용할 것이니 Stack 의 시간복잡도를 복습해야겠다. 

 

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert (push)	O(1)	O(1)
Delete (pop)	O(1)	O(1)

• 결국 시간복잡도는 O(n)정도일 것 같다.
• 삽입은 최대 10만번 될 수 있다. s에 '('가 10만개인경우  -> 항상 맨위에 넣으므로 시간복잡도가 O(1)이라 상수시간이고, 결국 최대 10만번이다.
• empty()역시 비었는지 안비었는지만 확인하면 되기 때문에 O(1)이다. 

 

엄청 큰데이터도 아니고, 스택의 함수역시 빠른 애들만 사용되기 떄문에 복잡도를 고려할정도는 아닌것 같다. 

 

 

2. 수도코드/ 알고리즘 생각

문자열의 끝까지 반복한다.

1. 열린괄호 '(' 를 만나면 스택.push(  '('  )
2. 닫힌괄호 ')'를 만나면
   •  스택이 비었는지 확인 - 닫힌괄호를 만났으니 뺄게 있어야함 > 비었으면 바로 false를 때린다. 
   • 스택.pop  
3. 반복문이 끝났을 때 스택이 비어있으면 올바른 괄호이다. 

 

 

✅ 내가 쓴 정답코드

import java.util.*;
class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        int length = s.length();
        for (int i= 0 ; i< length ; i++ ) {
            Character now = s.charAt(i);

            if (now == '(') {
                stack.push(now);
            }
            else { //now == ')'
                if (stack.empty()) {
                    return false;
                }
                stack.pop();
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }
}

 

 

 

 

 

---

references

프로그래머스 

https://m.blog.naver.com/justkukaro/220503515118

https://propercoding.tistory.com/17