[프로그래머스][java] lv 2 올바른 괄호

1. 문제 설명

 

2. 나의 풀이

    public static boolean solution(String s) {
        boolean answer = true;
        int cnt = 0;
        for(int i = 0; i < s.length(); i++)
		{
        	if(s.charAt(0) == ')')
			{
				return false;
			}
        	if(s.charAt(i) == '(')
			{
				cnt++;
			}
        	else
        	{
        		cnt--;
        	}
		}
        if(cnt != 0){answer = false;}
        	
        return answer;
    }

처음 짠 오답 ;;

스택으로 풀고 싶었는데 안 써봐서 어떻게 해야할지 모르겠더라.

gpt 선생님께 문제 주고 힌트 달랬더니 카운트로 푸는 걸 권장한대서 이렇게 짰음

틀린 이유

첫 번째 문자가 )인지 확인하는 조건 if(s.charAt(0) == ')')가 너무 초기 단계에서만 검사되고, 이후의 균형을 확인하지 않음.괄호의 균형을 확인하려면 카운터가 음수가 되는 순간을 바로 false로 처리해야 함.

즉, cnt 값이 음수가 되는 경우는 이미 닫는 괄호 )가 여는 괄호 (보다 많아졌음을 의미하므로, 그 즉시 false를 반환.

 

수정한 코드

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int cnt = 0;
        for(int i = 0; i < s.length(); i++)
		{
        	if(s.charAt(i) == '(')
			{
				cnt++;
			}
        	else
        	{
        		cnt--;
        	}
        	if(cnt < 0){return false;}
		}	
        return cnt == 0;
    }
}

1. for문 안에서 cnt가 음수가 되는지 확인하여, 균형이 깨지는 즉시 return false

2.cnt == 0 이어야 균형이 맞는 것이므로 if(cnt == 0){answer = true;} 할 필요 없이 그냥 바로 비교식을 return해줌

 

 

3. 다른 사람의 풀이

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        boolean answer = true;  
        String res = "YES";
        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    st.push(1);
                } else if (s.charAt(i) == ')') {
                    if (st.isEmpty()) {
                        answer = false;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }

            if(!st.isEmpty()) {

                answer = false;

            }

            System.out.println(res);
return answer;
    }   

}

Jungjin Park 님의 풀이.

stack으로 푼다면 어떻게 풀어야할지 참고하려고 갖고왔다.

빈 스택에 push로 '(' 나 ')' 가 아닌 그냥 아무거나 넣어도 되는구나! 

나는 아직 이런 발상을 잘 못하는 것 같다..문제에서 ( )가 나오고 스택이면 당연히 스택에 (을 넣을 생각부터 한다.

(가 나오면 1을 넣고, 짝이 맞으면 다시 pop으로 빼내고.

최종적으로 st이 비어있어야 true를 반환하는 방식이다. 다음에 스택/큐 문제가 나오면 써봐야겠다,