올바른 괄호 (programers > lev2 > Stack_Queue)

문제 링크

문제설명

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

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

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

제한사항

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

입출력 예

입출력 예 설명

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

풀이

   static boolean solution(String s) {
        boolean answer = true;
        
        //애초에 stk에는 (밖에 없음! )는 나오는 즉시 제거할지 말지에만 관여하기때문
        Stack<Character> stk = new Stack<Character>();
        
        for(int i=0;i<s.length();i++) {
        	if(s.charAt(i) == '(')
        		stk.push('(');
        	
        	else { //들어갈 준비중인게 )
        		if(stk.isEmpty())
        			return false;
        		else
                    stk.pop();
        	}
        }
        
        if(!stk.isEmpty())
        	return false;
        
        return answer;
    }

후기 (13min but…)

풀기는 십분만에 푼거같은데 효율성에서 계속 걸렸다!! 으아 이것때문에 삼십분 잡아먹음

괄호관련 스택문제 풀 때 항상 if를 어떻게 걸어줄지를 열심히 고민하는데 이번에 효율성에서 통과하면서 확실히 느낀점은

1. STACK에는 ‘(‘ 밖에 들어가지 않는다.
2. ’)’는 PEEK인 (를 지우느냐 마냐 에만 관여한다는 것이다.
3. 따라서 이 코드에 ‘)’를 push하는 함수는 없다는 것!
4. stack에 (밖에 없고 size도 0이 아니라면 )가 할 수 있는건 pop()밖에 없다!!

tip

1. 오랜만에 풀었는데 조건 거는 법을 자꾸 까먹는다..
2. 효율성을 위해 조건을 깔끔하게 거는 법, 더 간단한 방법 생각하기!