Codility Lesson 7-1: Brackets

yoogail·2022년 5월 22일
0

Algorithm

목록 보기
12/12
post-thumbnail

🤔 문제분석

  • 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
}

🔖 문제 출처 및 참고

profile
🍫 iOS 🍫 Swift

0개의 댓글