2월 3일 TIL

프로그래머스 코딩테스트 [ 괄호 회전하기 ]

Github 링크

• 이 문제는 주어진 String이 올바론 괄호 문자열인지를 확인하고, 문자열을 회전하면서 총 몇번의 올바른 문자열이 등장하는지를 확인하는 문제이다.
• 올바른 괄호 문자는 [],(),{}, 이 세개로 구성이 되어 있으며, 괄호 안에 괄호도 문제가 없다. 단 "{{](" 이런식으로 완성이 되지 않는 괄호는 올바르지 않다고 판단하는것이다.
• 난 그래서 Stack을 사용하기로 하였다. Stack에 하나하나 쌓으면서, stack.suffix(2)가 만약 [],(),{},이 된다면 removeLast(2)를 통해 stack을 비우고, 만약 모든 문자열을 다 순회했을때 stack이 비어있다면, 올바른 괄호 형식을 갖은 문자열이라는걸 알 수 있다. 아래가 내가 작성한 코드다.

import Foundation

func solution(_ s:String) -> Int {
    var ans = 0
    var s = s
    var stack : [String] = []
    var check = [["[","]"],["{","}"],["(",")"]]
    let n = s.count
    for _ in 1...n{
        for char in s {
            stack.append(String(char))
                if check.contains(stack.suffix(2)){
                    stack.removeLast(2)
                }
        }
        if stack.isEmpty{
            ans += 1
        }
        stack = []
        let first = s.removeFirst()
        s.append(first)
    }
    
    return ans
}

• 모든게 완벽한줄 알았지만, 첫번째 테스트케이스에서만 시간초과가 떴다. 아마 문자열의 최대 길이인 1000으로 주어졌을때 시간초과가 뜬거라고 생각을 했다. 그래서 만약 stack을 확인하는 횟수를 줄인다면 조금이나마 시간을 줄일수 있지 않을까 싶어서, 생각해보니 stack을 확인해야하는 시점은 결국 괄호가 닫히는 경우에만 확인해도 되니깐, 조건문 하나를 추가해서 check.contains(stack.suffix(2)를 최소한으로 불릴수 있도록 했다.

import Foundation

func solution(_ s:String) -> Int {
    var ans = 0
    var s = s
    var stack : [String] = []
    var check = [["[","]"],["{","}"],["(",")"]]
    let n = s.count
    for _ in 1...n{
        for char in s {
            stack.append(String(char))
            if String(char) == "}" || String(char) == ")" || String(char) == "]"{
                if check.contains(stack.suffix(2)){
                    stack.removeLast(2)
                }else{
                    break
                }
            }
        }
        if stack.isEmpty{
            ans += 1
        }
        stack = []
        let first = s.removeFirst()
        s.append(first)
    }
    
    return ans
}

• 위 처럼하니깐 시간을 획기적으로 줄일수 있었다.
• 다른사람의 풀이를 보니깐, String.replaceOccurence() 통해서 계속 지워주는 방식으로 코드를 짠 사람도 있었다. 나는 replace 방법이 시간복잡도가 높다는걸로 알고 일부러 안썻는데, 결국 똑같이 시간초과가 뜨는거라면 비교적 쉬운 저방법도 써볼걸 그랬다.
• 내가 짠 코드가 완벽하고, 가독성도 좋고 그런건 아니지만, 내가 당장 생각할수 있는 선에서 예외처리, 불필요한 작업들을 반복적으로 수행하지 않도록 코드를 짜는것도 중요한것 같다.