프로그래머스 - L2 짝지어 제거하기

설계

문자열을 순회해서 stack에 넣기 전에 맨 윗부분을 검사해서 같은 경우 pop, 다른 경우 push

순회가 끝났을 때 stack이 빈 경우면 조건에 만족

git : 짝지어 제거하기

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12973

---

문제 풀이

if let peek = stack.last 에서 nil 인 경우 stack이 빈 경우이므로 stack.append(alphabet) 추가하기

nil이 아닌 경우 peek 값과 순회하는 알파벳을 확인하여 같은 경우면 연속적이기 때문에 pop 아닌 경우 추가해주기

func solution(_ s:String) -> Int{
    var answer:Int = 0
    var stack: [String] = []
    
    s.forEach { char in
        let alphabet = String(char)
	        if let peek = stack.last {
	            if(peek == alphabet) {
	                stack.popLast()
	            } else {
	                stack.append(alphabet)
	            }
	        } else {
	            stack.append(alphabet)
	        }
    }
    if(stack.isEmpty == true) {
        answer = 1
    }
    
    return answer
}

?!??! 위와 같이 채점을 돌렸더니, 효율성검사 2번에서 시간초과가 나왔습니다;;

O(n)로 생각했는데… 혹시나 .last를 공식문서에 찾아봤는데 O(1) 이여서 멘붕…

그래도 혹시나 .last를 stack[count-1]로 아래와 같이 변경해봤습니다.

func solution(_ s:String) -> Int{
    var answer:Int = 0
    var stack: [String] = []
    
    s.forEach { char in
        let alphabet = String(char)
        
        if(stack.isEmpty == true) {
            stack.append(alphabet)
        } else {
            let peek = stack[stack.count-1]
            
            if(peek == alphabet) {
                stack.popLast()
            } else {
                stack.append(alphabet)
            }
        }
    
    if(stack.isEmpty == true) {
        answer = 1
    }
    
    return answer
}

결과는 통과..! 뭐지.. 아무래도 옵셔널 처리에서 시간이 소요되는거 같다고 추측..해봅니다 허허

// [count-1]
//테스트 1 〉    통과 (206.25ms, 25.1MB)
//테스트 2 〉    통과 (167.51ms, 17.3MB)
//테스트 3 〉    통과 (176.85ms, 21MB)
//테스트 4 〉    통과 (177.03ms, 21MB)
//테스트 5 〉    통과 (178.12ms, 20.9MB)
//테스트 6 〉    통과 (167.07ms, 21.1MB)
//테스트 7 〉    통과 (176.54ms, 20.8MB)
//테스트 8 〉    통과 (178.27ms, 24.9MB)

// .last
//테스트 1 〉    통과 (289.37ms, 25.2MB)
//테스트 2 〉    통과 (224.05ms, 17.6MB)
//테스트 3 〉    통과 (290.78ms, 21MB)
//테스트 4 〉    통과 (289.27ms, 20.8MB)
//테스트 5 〉    통과 (286.54ms, 21MB)
//테스트 6 〉    통과 (288.91ms, 21.1MB)
//테스트 7 〉    통과 (272.86ms, 21MB)
//테스트 8 〉    통과 (289.86ms, 25.2MB)

차이가 나긴하네요.. .last로 처리한걸 다시 돌렸을 땐 통과하긴 하더라구요..

어디까지나 추측이니.. 다른 의견 있으시면 댓글 달아주시면 감사하겠습니다!

다른 사람 풀이 분석

프로그래머스 - 이승언 님

func solution(_ s:String) -> Int {
    if s.count % 2 != 0 { return 0 }
    var temp = [Character]()

    for char in s {
        if temp.last == char {
            temp.removeLast()
        } else {
            temp.append(char)
        }
    }

    if temp.isEmpty { return 1 }
    else { return 0 }
}

메커니즘은 동일하나 해당 풀이에서는 if s.count % 2 != 0 { return 0 } 홀수 인 경우 처리를 해주셨네요..

효율적인 방법 같아 소개해드립니다!

정리

옵셔널 언래핑 시간소요?!?

---