코드챌린지 문자열 스택 괄호회전하기 스위프트 언어 문제풀이

 

 

안녕하세요. 멍구입니다. 😁

 

한번씩 프로그래머스 사이트를 들어가면 새로 생긴 문제가 있는데요. 그중에 쉬운문제는 한번씩 풀어보게 되네요.

오늘 풀어볼 문제는 프로그래머스 월간 코드챌린지 시즌2에 초반부 문제로 출제 된 괄호회전하기 문제입니다.

 

괄호 하면 스택이 떠오를 만큼 자주 볼 수 있는 문제죠. 카탈란수와도 관련이 있을 수 있는 괄호문제인데, 이번 문제는 스택원리만 잘 활용하면 쉽게 풀 수 있는 문제였습니다. 바로 가보도록 하겠습니다~

 

 

---

프로그래머스 코드챌린지 괄호회전하기 문제 설명

코딩테스트 연습 - 괄호 회전하기

해당 문제의 설명은 위 링크를 통해 보실 수 있습니다. 괄호 문자열이 주어졌을때, 해당 괄호 문자열이 문자열 길이만큼 한칸씩 회전 시켜보았을때 올바른 괄호가 되는 경우의 수를 구하는 문제입니다. 

 

문제 풀이 바로 시작해보도록 하겠습니다.

 

 

---

프로그래머스 코드챌린지 괄호회전하기 문제 스택활용 swift 풀이

먼저, 보다 편하게 문자열의 문자를 접근하기 위해 입력받은 s 문자열에 대해 [Character] 배열 타입의 array를 만들어줬습니다. 또한 해당 배열의 길이를 count에 저장했습니다. String타입의 문자열에도 count 프로퍼티를 통해 문자열 길이를 구할 수 있지만, String타입의 count 시간복잡도는 O(N)임을 유의해야 합니다. Array의 count 시간복잡도는 상수복잡도이죠.

 

그 다음 reduce 를 통해서 올바른 괄호의 갯수를 카운팅 하려합니다.

 

 

 

reduce의 초기값은 0으로, answer 값이 0으로 시작하게 됩니다. 올바른 괄호 케이스가 생길때마다 1씩 카운팅이 되어 답으로 반환이 됩니다. startIndex는 0부터 array.count - 1까지, array의 계수가능 범위를 초기 시작 인덱스 기준으로 차례대로 잡고 탐색하게 됩니다. array.indices가 array의 계수가능범위를 의미합니다. 

 

5행) stack으로 사용할 [Character] 배열을 하나 선언했습니다. 해당 배열에는 "[", "(", "{" 세가지의 문자만 들어갑니다. 이렇게 들어간 문자는 "]", ")", "}" .... 등의 문자가 들어올때 이에 매칭되는 괄호가 이전에 있었는지를 체크하기 위해 사용하게 됩니다. 

 

7 ~ 8행) 앞서 startIndex를 기준으로 array 길이만큼 탐색을 하며, 올바른 괄호인지를 체크합니다. 8행에서는 참고할 인덱스 값이 count를 나머지 연산 처리함으로서 괄호를 일일히 회전할 필요없이 인덱스가 끝에 도달했을때 처음으로 돌아갈 수 있게 해줍니다.

 

9 ~ 23행) 올바른 괄호인지를 체크하는 과정입니다. stack에 들어갈 문자라면 넣어주고, 그게 아니고 stack에 값이 있을경우, 현재 탐색하는 문자가 stack.last!와 매칭되는지 체크합니다. 이때 괄호가 매칭이 되지 않으면 false입니다. 이외에도 탐색하는 문자가 있는데도 stack이 비어있을경우 false입니다. 

 

24행) 최종적으로 괄호 체크를 할때 문제가 없었고 (good == true), 괄호체크에 사용한 stack이 비어있을 경우 현재 회전되어있는 괄호 문자열은 올바른 괄호임을 의미합니다. 이 경우 answer += 1 처리를 해줍니다.

 

결과적으로 reduce 연산 끝에 올바른 괄호의 경우의 수 카운팅 결과, answer 가 반환되며 문제를 해결할 수 있습니다.

저처럼 reduce를 사용하실 수도 있고, 그냥 forEach, for in 루프를 사용하셔도 문제 없습니다. 또한 "[", "(", "{", "]", "}", ")" 등의 문자에 대한 정보를 딕셔너리나 배열로 미리 기억해두고 활용하면 보다 가독성 있는 코드로 문제를 풀 수도 있을 것 같습니다.

 

이렇게 결과적으로 프로그래머스 코드챌린지 시즌2 / 2단계 문제, 괄호회전하기 문제는 스택의 원리를 활용하면 쉽게 풀 수 있는 2단계 문제였습니다.

 

아래는 swift 문제풀이 제출결과 및 전체 소스코드입니다.

질문이나 의견 자유롭게 공유 부탁드립니다. 즐거운 코딩 되세요!! 👨🏻‍💻

 

 

 

---

프로그래머스 코드챌린지 괄호회전하기 swift 알고리즘 문제풀이 결과

 

 

 

---

swift 전체 소스코드

func solution(_ s: String) -> Int {
    let array = Array(s)
    let count = array.count
    return array.indices.reduce(into: 0) { (answer, startIndex) in
        var stack: [Character] = []
        var good: Bool = true
        for originIndex in array.indices {
            let index = (originIndex + startIndex) % count
            let char = array[index]
            if char == "[" || char == "(" || char == "{" {
                stack.append(char)
            } else if stack.isEmpty == false {
                if stack.last! == "[" && char == "]"
                || stack.last! == "(" && char == ")"
                || stack.last! == "{" && char == "}" {
                    stack.removeLast()
                } else {
                    good = false; break
                }
            } else {
                good = false; break
            }
        }
        answer += good && stack.isEmpty ? 1 : 0
    }
}