lv.2 올바른 괄호 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> stack = new Stack<char>();

        for (int i = 0; i < s.Length; i++)
        {
            if (s[i].Equals('('))
            {
                stack.Push(s[i]);
                continue;
            }

            if(s[i].Equals(')'))
            {
                if(stack.Count == 0 || stack.Peek() == ')')
                {
                    return false;
                }

                stack.Pop();
            }
        }

        return stack.Count == 0;
    }
}

• 문제를 해석해보면, 주어지는 괄호는 반드시 바르게 짝지어져야 한다.
  • 문제에 맞는 자료구조를 생각해 보았을 때, 여는 괄호와 짝이 지어지려면 다음번의 닫는 괄호와 연결시켜주어야 하는데, 구조를 생각해 보았을 때 Last in First out의 Stack을 사용하면 된다.

✍️ 중요 포인트

• 시간복잡도는 최대 O(n)으로 반복문으로 문자열 ‘s’의 문자를 순회하여 해결한다.
• 조건으로는 Stack을 활용해 여는 괄호가 들어왔을 땐 Push로 담아준다.
• 닫는 괄호가 들어왔을 땐 Stack의 Count가 0인지를 확인하고 Peek 함수를 사용해 저장해 놓았던 데이터를 확인했을 때 여는 괄호가 아닌 닫는 괄호가 나온다면 false를 반환한다.
• 닫는 괄호가 들어오고 Peek함수를 사용해 데이터를 확인했을 때, 여는 괄호와 짝지어 지면 그때 Pop함수를 사용해 Stack의 데이터를 뽑아 Count 수를 낮춘다.
• 반복문 탈출 후 Stack의 Count가 0이면 True를 반환한다.

---

다른 사람의 풀이 코드

using System;

public class Solution {
	  public bool solution(string s)
	  {
	    int length = s.Length/2;
	
	  for(int i=0; i< length; i++)
	  {
	      s = s.Replace("()", "");
	  }
	
	    return s.Length >= 1 ? false : true;
	  }
}

• 이 분의 코드를 해석해보면 주어지는 문자열의 길이를 2로 나눈다. 이유는 다음 Step인 반복문에서 알 수 있는데, s의 문자열 중 Replace 함수를 사용하여 짝지어지는 괄호를 빈 문자로 변경한다.
  • 짝지어주는 문자열의 갯수는 2개이기 때문에 한 번에 2개의 문자열을 빈 문자로 변경하기 때문에 처음 문자열의 길이를 2로 나눈 값을 반복문으로 돌린 것이다.
• 반복문 탈출 후 s 문자열의 길이가 1보다 같거나 크면 false, 작다면 true를 반환한다.