Codility Lesson 7-1: Brackets

🤔 문제분석

• N개의 캐릭터들을 가지고 있는 String S
• 다음의 조건 중 하나라도 ture이면 nested된 것으로 간주
• nested면 1, 아니면 0을 return
• Lesson 7은 Stack & Queue

return 1인 조건

1. S는 비어있음
2. S는 U가 중첩된 스트링일 때 "(U)" or "[U]" or "{U}"의 형태를 가짐
3. S는 V와 W가 중첩된 스트링일 때 VM을 형태를 가짐

예를 들어,

• {[()()]}는 nested → 1
• ([)()]는 nested(X) → 0

조건

• N은 0부터 200,000 사이의 Int
• string S는 (, {, [, ], }, )만 가짐

✍️ Solution

🖍 첫 번째 시도

• String을 Character을 가진 배열 charArray로 변경
• 배열을 돌면서 char가 {, [, (이면 stack에 넣음
• 짝을 이루어야 할 원소가 남아있는데 stack이 비어있으면 0을 리턴(짝이 안맞는 것이므로)
• 알맞은 짝이 현재 stack의 top에 없으면 return 0 (짝 X)

public func solution81(_ S : inout String) -> Int {
    let charArray = Array(S)
    var stack: [Character] = []
    let count = charArray.count
    var topChar: Character
    
    // 홀수이거나 엘레멘트가 없을 때 리턴 0
    if count % 2 != 0 || count == 0 {
        return 0
    }
    
    
    for char in charArray {
        if char == "{" || char == "[" || char == "(" {
            stack.append(char)
        } else {
        	// 짝을 이루어야 할 원소가 남아있는데 stack이 비어있으면 0을 리턴(짝이 안맞는 것이므로)
            if stack.isEmpty { return 0 }
            topChar = stack.popLast()!
            
            if char == "}" && topChar != "{" ||
                char == "]" && topChar != "[" ||
                char == ")" && topChar != "(" {
                return 0
            }
        }
    }

    return 1
}

결과

🖍 두 번째 시도

놓친부분

• empty string일 때 1리턴
• char를 돈 후에, stack이 비어있지 않았으면 return 0 (짝 X) 추가

  // empty string일 때 1리턴
 if count == 0 {
        return 1
}

// 짝이 맞지 않았을 때 0 리턴
if !stack.isEmpty {
        return 0
}

전체 코드

public func solution(_ S : inout String) -> Int {
    let charArray = Array(S)
    var stack: [Character] = []
    let count = charArray.count
    var topChar: Character
    
    // empty string일 때 1 리턴
    if count == 0 {
        return 1
    }
    
    // 홀수일 때 0 리턴
    if count % 2 != 0 {
        return 0
    }
    
    
    for char in charArray {
        if char == "{" || char == "[" || char == "(" {
            stack.append(char)
        } else {
            if stack.isEmpty { return 0 }
            topChar = stack.popLast()!
            
            if char == "}" && topChar != "{" ||
                char == "]" && topChar != "[" ||
                char == ")" && topChar != "(" {
                return 0
            }
        }
    }
    
    if !stack.isEmpty {
        return 0
    }

    return 1
}

• 결과: 100%
  
  

🔖 문제 출처 및 참고

• Codility Lesson 7-1: Brackets
• hyeonmin-yoo/Codility-Swift