[C#][프로그래머스] 올바른 괄호

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

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

 

📒 문제

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

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

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

 

제한사항

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

 

입출력 예

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

 

입출력 예 설명

 

입출력 예 #1,2,3,4

• 문제의 예시와 같습니다.

---

💻 소스코드

using System;
using System.Collections.Generic;

public class Solution {
    public bool solution(string s) {     
        Stack<char> st = new Stack<char>();
        bool answer = true;
        for(int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(') st.Push(s[i]);
            if (s[i] == ')')
            {
                if (st.Count == 0)
                {
                    answer = false;
                }
                else if (st.Peek() == '(')
                {
                    st.Pop();
                }
            }
        }
        if (st.Count > 0) answer = false;
        
        return answer;
    }
}

 

다른풀이

using System;

public class Solution {
    public bool solution(string s) {       
        int count = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
                count++;
            else
                count--;

            if (count < 0) return false;
        }
        return count == 0;
    }
}

 

📝 풀이

코드1

스택을 이용해서 문제를 해결했다.

')' 인 경우에 ()를 완성시킬게 없거나 반복문을 다돌았을때 스택에 요소가 남아있으며 false를 return하였다.

 

코드2

다른 풀이를 찾아보다 좋은 아이디어라 생각해 가져왔다.

'(' 인경우 +1을 ')'경우 -1을 해서 결과가 0이면 괄호를 모두 완성한것으로 아니면 완성하지 못한것으로 return하였다.

 

오답노트

using System;

public class Solution {
    public bool solution(string s) {
        while(s.IndexOf("()") > -1)
        {
            s = s.Replace("()", "");
        }
        return s == "";
    }
}

 

오답1

위 오답은 결과는 맞지만 효율성 테스트에서 오답처리 되었다.
indexof와 replace가 내부적으로 계속 반복문을 돌기때문에 s가 너무 길면 오래걸리 수 있다.

 

using System;

public class Solution {
    public bool solution(string s) {
        if (s[0] == ')' || s[s.Length - 1] == '(') return false;
        
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(') left++;
            else right++;
        }
        
        return left == right;
    }
}

 

오답2

위 오답은 "())((()))(()" 처럼 '('와 ')' 개수는 동일하지만 괄호를 완성 시키지 못하는 경우를 걸러내지 못한다.

 

 

---

관련 포스팅

[자료구조] 스택 (Stack)