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

문제 설명

나의 풀이

import Foundation
func solution(_ s:String) -> Bool {
    var ans:Bool = false
    var stack: [Character] = []
    // 개수가 홀수인 경우
    if s.count % 2 == 1 { 
        return ans
    }
    // 첫 시작이 )인 경우
    if s.first == ")" { 
        return ans
    }
    // 마지막이 (인 경우
    if s.last == "(" {
        return ans
    }
    
    var countLeft = s.filter { $0 == "(" }.count
    var countRight = s.filter { $0 == ")" }.count
    // (의 개수와 )개수가 안 맞는 경우
    if countLeft != countRight { 
        return ans
    }
    
    for char in s {
        if stack.isEmpty {
            stack.append(char)
        }
        else if char == "(" {
            stack.append(char)
        }
        else if char == ")" {
            if stack.last == "(" {
                let _ = stack.popLast()
            }
            else {
                return ans
            }
        }
    }
    
    if stack.count > 0 {
        return ans    
    }
    return true
}

고민한 점

처음에 stack으로 시도했을 때 앞에서 걸러주는 가지의 수가 적을 때 효율성을 통과하지 못했다. 현재 코드에서도 효율성 1번은 통과하지 못했다.

그리고 popLast()와 removeLast()의 시간복잡도는 O(1)로 같다고 나오는데 제거해주는 부분을 popLast()로 했을 때는 정확성 모두 통과, removeLast()로 했을 때는 2개가 실패로 나오는데 왜 그런기 모르곘다.. 또한 마지막 검사구문에서 개수를 확인할 때 count를 썼을 때와 isEmpty를 썼을 때에도 정확도에서 문제가 발생하는데 이유를 모르겠다..

수정한 코드

import Foundation

func solution(_ s:String) -> Bool {
    var ans:Bool = false
    var stack = 0
    
    for char in s {
        if char == "(" {
            stack += 1
        }
        else {
            if stack == 0 {
                return ans
            }
            else {
                stack -= 1
            }
        }
    }
    
    if stack > 0 {
        return ans    
    }
    
    return true
}

기존의 앞에서 조건들을 걸러주거나, 실제로 스택에 넣었다 뺐다 하는 것이 아니라 카운트만 하는 형식으로 바꾸니 효율성을 통과할 수 있었다..

참고

Programmers