[프로그래머스] 괄호 회전하기 (Swift) (스터디)

https://programmers.co.kr/learn/courses/30/lessons/76502

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

1. 적용 알고리즘과 문제 설명

구현 문제

괄호들로 구성된 하나의 문자열이 주어지면 이 괄호 문자열이 짝이 맞는 괄호들로 구성되어 있는 올바른 문자열인지 검사해야 한다.

근데? 이 문자열만 검사하는게 아님. 이 문자열을 한칸씩 오른쪽으로 밀어서 회전한 모든 문자열들에 대해서도 검사를 해야함

그래서 과연 몇개나 올바른 문자열인지 그 개수를 반환해야 함

이 문제에서 회전한 문자열을 구하는 데 사용한 방법을 그림으로 그려봤다 ^_^ (친절MAX)

이런 방식으로 문자열은 그대로 두고 인덱스의 시작 위치만 바꿔가면서 회전한 문자열을 순회했다

인덱스가 끝에 도달하면 (인덱스 % n)를 사용하여 0번으로 옮겼다.

그리고 인덱스가 start와 동일해지면 문자열을 모두 봤다는 뜻이므로 반복문을 종료했다.

 

올바른 문자열인지 검증할 때에는 stack 자료구조를 사용하여(swift의 array에서 stack에 필요한 대부분의 메서드를 제공하기 때문에 array를 사용함) 현재 인덱스가 가리키는 문자가 여는 괄호면 스택에 넣고,

닫는 괄호면 스택이 비었거나 (짝이 맞는 여는 괄호가 없으므로 올바르지 않은 문자열), 스택의 맨 위에 있는 문자가 현재 문자(닫는 괄호)와 짝이 맞지 않으면 isRightStr을 false로 바꾸고 반복문을 나오면 된다 (더 볼 필요가 없으므로)

 

반복문을 나왔을 때 즉, 하나의 문자열에 대한 검증을 끝냈을 때

isRightStr 변수가 true이고, 스택도 비었다면 이는 올바른 문자열이므로 올바른 문자열의 개수를 담은 변수인 result 변수를 1 증가시킨다. 그리고 한번 더 회전한 문자열에 대해서 같은 일을 반복한다.

2. 코드에 대한 설명

import Foundation

func solution(_ s:String) -> Int {
	// 닫는 괄호와 여는 괄호를 매핑
    let bracketMap:[Character:Character] = [")":"(", "}":"{", "]":"["]
    
    let sArray:[Character] = Array(s)
    let n:Int = sArray.count
    var result:Int = 0
    
    // 괄호 문자열의 시작점(start)를 한칸씩 옆으로 이동하면서 괄호 문자열을 회전하는 반복문
    for start in 0..<n {
    	// 닫는 괄호로 문자열이 끝났을 경우("()}}"를 대비하여 isRightStr 변수 사용
        var isRightStr:Bool = true 
        var stack:[Character] = []
        var index:Int = start
        // 괄호 문자열이 올바른 괄호 문자열인지 검증하기 위해 문자열을 순회
        repeat {
        	let currentChar:Character = sArray[index]
            if currentChar == "(" || currentChar == "{" || currentChar == "[" {
                stack.append(currentChar)
            } else if stack.isEmpty || stack.removeLast() != bracketMap[currentChar] {
                isRightStr = false
                break
            }
            index = (index+1) % n
        } while index != start
        
        if isRightStr && stack.isEmpty { 
            result += 1
        }
    }
    return result
}

4. 시간 복잡도, 공간 복잡도 계산

시간 복잡도

길이가 n인 문자열이 입력되면, 이를 회전한 문자열이 n개 생김

ex. {()} -> {()}  ,  ()}{  ,  )}{(  ,  }{() 

하나의 문자열에 대해 최악의 경우 해당 문자열의 모든 문자(n개)를 순회하며

stack에 append (O(1))하거나 stack에서 빼는 작업(O(1))을 해야하기 때문에

하나의 문자열이 올바른 문자열인지 검증하는 데에 드는 시간복잡도는 O(n)

회전한 문자열이 총 n개 생기므로 O(n*n) -> O(n^2)

 

공간 복잡도

올바른 괄호 문자열인지 검증하는 과정에서 stack(array)자료구조 사용

최악의 경우 stack에 문자열 전체가 push되기 때문에 O(n)만큼의 공간복잡도

5. 사용 라이브러리

Array의 메서드

- append(Int) : O(1)

- removeLast() : O(1)

6. 문제 풀이에 어려웠던 점

하나의 문자열에 대한 순회를 마쳤을 때 스택이 비었는지만 확인하면

짝을 맞추지 못한 닫는 괄호로 문자열이 끝났을 경우에 예외가 발생하는 점을 해결해야 했다.

boolean 타입의 isRightStr 사용하여 해결함