[Algorithm] 프로그래머스 짝지어 제거하기

문제 설명

나의 풀이

틀린 풀이

import Foundation
let possibles = ["aa","bb","cc","dd","ee","ff","gg","hh","ii","jj","kk","ll","mm","nn","oo","pp","qq","rr","ss","tt","uu","vv","ww","xx","yy","zz"]
func solution(_ s:String) -> Int{
    var answer = 1
    var sCopy = s
    var before = sCopy
    while true {
        before = sCopy
        if sCopy.count == 0 {
            break
        }
        else if sCopy.count == 1 {
            return 0
        }
        
        for i in 0..<possibles.count-1 {
            if sCopy.contains(possibles[i]) {
                sCopy = sCopy.replacingOccurrences(of: possibles[i], with: "")
            }
        }
        
        if before == sCopy {
            return 0
        }
    }
    return answer
}

효율성은 당연히 통과하지 못했고, 정확성에서도 문제가 발생했다..

수정한 풀이

import Foundation

func solution(_ s:String) -> Int {
    if s.count % 2 == 1 {
        return 0
    }
    var stack: [Character] = []
    for i in s {
        if stack.last == i {
            stack.removeLast()
        } else {
            stack.append(i)
        }
    }
    return stack.isEmpty ? 1 : 0
}

일단 개수가 홀수인 경우에는 어떻게 제거해도 1개가 남기 때문에 첫 조건에서 걸러줄 수 있다. 그리고 중요한 건 바로 stack의 개념을 사용하는 것이였다.. stack의 top과 같으면 제거, 그렇지 않으면 추가, 이렇게 하면 O(N)이라는 시간복잡도안에 해결할 수 있다.

괜찮은 남의 풀의

수정한 코드가 다른 사람의 코드를 보고 작성한 것이므로 생략

참고

Programmers