[Algorithm/Swift] Codility / Brackets

문제

https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

풀이

[ { ( ) } ] 적절하게 중첩된 문자열인지 체크하는 문제입니다.

가로는 항상 올바르게 중첩이 된 상태여야 합니다.

[ { ( } ) ] 이렇게 되면 짝은 맞지만 올바른 중첩은 아닙니다.

Stack를 이용해서 풀어봅시다.

Code

public func solution(_ S : inout String) -> Int {
    
    var stack:[Character]  = []
    var valid = true
    
    for i in S {
        
        if i == "[" {
            stack.append(i)
        } else if i == "{" {
            stack.append(i)
        } else if i == "(" {
            stack.append(i)
            
        } else if i == ")" {
            if stack.last == "(" {
                stack.popLast()
            } else {
                valid = false
            }
        } else if i == "}" {
            if stack.last == "{" {
                stack.popLast()
            } else {
                valid = false
            }
        } else if i == "]" {
            if stack.last == "[" {
                stack.popLast()
            } else {
                valid = false
            }
        }
    }

    if valid == true {
        return 1
    } else {
        return 0
    }
}

 

왜이러는데,,

역시 코드는 가독성 필수,,, 

마지막에 한번 더 체크 !

Code O(N)

public func solution(_ S : inout String) -> Int {
    var stack:[Character]  = []
    var lastCharacter: Character
    
    for i in S {
        
        if i == "[" || i == "{" || i == "(" {
            stack.append(i)
        } else {
            if stack.isEmpty { return 0 }
            lastCharacter = stack.popLast()!
            
            if i == "}" && lastCharacter != "{" ||
               i == "]" && lastCharacter != "[" ||
               i == ")" && lastCharacter != "("
            {  return 0 }
        }
    }
    guard stack.isEmpty else {
        return 0
    }
    return 1
}