[프로그래머스] Swift - 괄호 회전하기 (LV.2)

👆문제풀러 가기👆

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

 

입출력 예제

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

 

풀이 [ 메모리: 16.7mb, 최대시간:  511.32ms ] 

func solution(_ s:String) -> Int {
    var s = s.map { String($0) }
    var count = s.count
    var result = 0

    while count > 0 {
        var stack = ""

        count -= 1

        for char in s {
            if let last = stack.last {
                if (last == "[" && char == "]") ||
                   (last == "(" && char == ")") ||
                   (last == "{" && char == "}") {
                    stack.removeLast()
                    continue
                }
            }
            stack.append(char)
        }

        if stack.isEmpty {
            result += 1
        }

        let cycle = s.removeFirst()
        s.append(cycle)
    }
    return result
}

 

문제를 받고 생각한 것.

1. 스택 유형의 단골문제인 괄호 문제.
2. 왼쪽으로 회전하는 괄호.
3. 현재 문자열이 정상적인 괄호의 집합인지 확인해야 한다.
4. stack의 마지막 element(last)가 push될 문자(char)와 같으면 stack의 마지막 element를 제거
5. 다르거나 stack이 비어있으면 char를 push
6. 위의 과정이 끝나고 stack이 비어있으면 정상 괄호이므로, result + 1
7. s의 첫번째 글자를 맨 뒤로 보내고, 첫번째 글자를 삭제한다.
8. 3~7과정 반복

이렇게 풀어도 괜찮고, 메서드를 활용하면 더 간결한 풀이가 가능하다.

다만 시간복잡도에서 다소 손해를 볼 수 있다.

 

다른 풀이 [ 메모리: 16.7mb, 최대시간:  9357.11ms ] 

func solution(_ s:String) -> Int {
    var brackets = s
    var s = s
    var result = 0

    for _ in s {
        while brackets.contains("[]") || brackets.contains("{}") || brackets.contains("()") {
            brackets = brackets.replacingOccurrences(of: "[]", with: "")
            brackets = brackets.replacingOccurrences(of: "{}", with: "")
            brackets = brackets.replacingOccurrences(of: "()", with: "")
        }

        if brackets.isEmpty {
            result += 1
        }

        let cycle = s.removeFirst()
        s.append(cycle)
        brackets = s
    }
    return result
}