[Swift 알고리즘] Brackets - Codility

Brackets coding task - Learn to Code - Codility

---

문제 분석 (오답)

문자열 S가 'properly nested' 문자열인지 판단하는 문제
 'properly nested'이란?
     1. "": 빈 문자열
     2. "(X)", "[X]", "{X}": 괄호로 둘러싸인 배열
     3. "XX": nested strings이 나열된 배열
 문자열 S는 (, ), [, ], {, } 으로만 구성된다.

 Stack으로 푸는 문제
 Stack을 구현하지 않아도 된다.

의사 코드 (오답)

3가지의 괄호를 담당하는 변수를 하나씩 선언한다.
 문자열을 탐색한다.
     열린 괄호를 만나면, 해당하는 변수에 += 1
     닫힌 괄호를 만다면, 해당하는 변수에 -= 1
     변수가 0 보다 작아지면, 즉시 return 0
 탐색이 종료되고, 3개의 변수가 모두 0이면 return 1 아니면 return 0

나의 풀이 (오답)

import Foundation
 import Glibc

 public func solution(_ S : inout String) -> Int {
     let size = S.count
     if size == 0 { return 1 }
     if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

     var bracket = 0
     var squareBracket = 0
     var curlyBracket = 0

     for i in 0..<size {
         let idx = S.index(S.startIndex, offsetBy: i)
         let currentBracket = S[idx]

         switch currentBracket {
             case "(":
                 bracket += 1
             case ")":
                 bracket -= 1
                 if bracket < 0 { return 0 }
             case "[":
                 squareBracket += 1
             case "]":
                 squareBracket -= 1
                 if squareBracket < 0 { return 0 }
             case "{":
                 curlyBracket += 1
             default: // "}"
                 curlyBracket -= 1
                 if curlyBracket < 0 { return 0 }
         }
     }

     return bracket == 0 && squareBracket == 0 && curlyBracket == 0 ? 1 : 0
 }

문제 분석 2 (오답)

Stack으로 구현해야 한다 ..
카운트만 해서는 다음과 같은 테스트 케이스를 통과할 수 없다. "([)()]"

의사 코드 2 (오답)

문자열을 담을 스택을 선언한다. var bracketStack = [String]()
 열린 괄호가 들어오면, 스택에 push() 한다.
 닫힌 괄호가 들어오면, 스택에서 pop() 한 값과 짝을 이루는지 검증한다.
     짝이 아니면 즉시 return 0
     짝이 맞으면 그대로 pop()
 탐색이 끝났을 때, 배열이 비어있으면 1 아니면 0

나의 풀이 2 (오답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

    var bracketStack = [String]()

    for i in 0..<size {
        let idx = S.index(S.startIndex, offsetBy: i) // 여기가 문제
        let currentBracket = String(S[idx])

        switch currentBracket {
            case ")":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "(" { return 0 }
            case "]":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "[" { return 0 }
            case "}":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "{" { return 0 }
            default:
                bracketStack.append(currentBracket)
        }
    }

    return bracketStack.count == 0 ? 1 : 0
}

// 시간 복잡도가 무려 O(3 ** N)...
// String의 subscript는 O(N)이다. RandomAccessCollection이 아니므로.
// 그렇다 하더라도 O(N ** 2) 아닌가? 찾아봤지만 답을 얻기 어렵다.

수정된 풀이 (정답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

    var bracketStack = [String]()

    for currentBracket in S {
				let currentBracket = String(currentBracket) // 이 부분 개선

        switch currentBracket {
            case ")":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "(" { return 0 }
            case "]":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "[" { return 0 }
            case "}":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "{" { return 0 }
            default:
                bracketStack.append(currentBracket)
        }
    }

    return bracketStack.count == 0 ? 1 : 0
}

// O(N)
// removerLast() -> Element
// popLast() -> Element?

더 나은 풀이 (정답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 }

    let bracketMap = [")": "(", "]" : "[", "}" : "{"]
    var bracketStack = [String]()

    for bracket in S {
        if let matchingBracket = bracketMap[String(bracket)] {
            if bracketStack.isEmpty || matchingBracket != bracketStack.last {
                return 0
            }
            bracketStack.removeLast()
        } else {
            bracketStack.append(String(bracket))
        }
    }

    return bracketStack.isEmpty ? 1 : 0
}

// 딕셔너리와 함께 하면 쉽다.
// switch를 활용하지 않아도 된다.

 

회고

가장 기본적인 문제인데 꽤 고생했다.

Swift의 문자열 인덱싱은 쉬이 익숙해지지 않는다.

 

Swift에서 subscript(_ :)는 기본적으로 O(1)을 보장하지만, String은 다르다.

String은 Character의 Collection이다.

C++, Java의 char는 고정된 크기를 갖지만, Swift의 Character는 1개 이상의 Unicode Scalar로 이루어져 있다. 크기가 가변적이다.

따라서 String은 RandomAccessCollection 프로토콜을 따르지 않는다. (BidirectionalCollection 채택)

따라서 순차 접근해야 한다.

그렇기에, index(_ : offsetBy:)로 접근해야 하고, O(N)의 시간복잡도를 갖는다.

 

길이를 구하는 .count 연산도 String은 O(N). RandomAccessCollection은 O(1).

 

String의 원소에 대한 임의 접근이 반드시 필요하다면?

String을 Character의 Array로 바꾸고 작업을 한 뒤, 마지막에 String으로 바꾸는 것이 좋다.

String.index를 순회하는 것보다, Character의 Array가 훨씬 효율적이다.

let str = "Hello, World!"
let arr = Array(str)

print(arr) 
// ["H", "e", "l", "l", "o", ",", " ", "W", "o", "r", "l", "d", "!"]

 

 

참고

https://jcsoohwancho.github.io/2019-11-19-Swift-String-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9C%BC%EB%A1%9C-%EC%93%B0%EA%B8%B0/

https://stackoverflow.com/questions/38800662/big-o-of-accessing-a-string-with-an-index-in-swift-3-0