[Algorithm] [Python/Swift] Programmers - 올바른 괄호

Programmers - 올바른 괄호

 

문제 설명

---

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

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

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

 

제한사항

---

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

 

제출 코드

---

Python

def solution(s):
    if s[len(s)-1] == '(':
        return False

    s = list(s)[::-1]
    cnt = 0

    while s:
        tmp = s.pop()
        if tmp == '(':
            cnt += 1

        elif tmp == ')':
            if cnt <= 0:
                return False
            else:
                cnt -= 1
    return False if cnt else True

 

Swift

import Foundation

func solution(_ s: String) -> Bool {
    let stack = Array(s)
    var cnt = 0

    if stack[stack.count - 1] == "(" {
        return false
    }

    for i in stack {
        if i == "(" {
            cnt += 1
        }
        else if i == ")" {
            if cnt <= 0 {
                return false
            } else {
                cnt -= 1
            }
        }
    }
    if cnt == 0 {
        return true
    } else {
        return false
    }
}

 

문제 풀이

---

스택의 성질을 이용하여 풀면 쉽게 풀어낼 수 있는 문제다.

0. 전달받은 매개변수 s의 제일 마지막 값이 '(' 인지 확인한다, 마지막 값이 열린 괄호라면 올바르지 못한 괄호다.

1. 전달받은 매개변수 s를 스택으로 사용하기 위해 이를 뒤집고 리스트로 변환한다.

2. 스택이 빌 때 까지 반복을 진행한다.

3. 원소 하나를 뽑고 해당 원소가 ( 인지, )인지 확인하여 이에 따라 분기한다.

4. (라면 올바른 괄호의 개수를 카운팅하기 위한 cnt 값을 1 올린다.

5. )라면 cnt값이 0보다 작은지 확인하여 작다면 false를 반환하고 그 외에는 cnt -= 1 연산을 진행한다.

6. 스택을 전부 순회했을떄, 올바른 괄호라면 cnt == 0을 만족하며, 올바르지 못하다면 cnt != 0이다. 따라서 이에 따라 적절한 값을 반환한다.