[프로그래머스] 짝지어 제거하기 - 효율성 통과하기

 
▼ 문제 링크

코딩테스트 연습 - 짝지어 제거하기

 

# 풀이 1
가장 첫 중복 요소를 확인하고 제거하는 함수 사용

import Foundation

func solution(_ s: String) -> Int{
    var chars = [Character]()
    var overlap = true
    
    s.forEach { // String을 [Character]로 변환
        chars.append($0)
    }
    
    repeat {
        overlap = checkOverlap(chars).0
        chars = checkOverlap(chars).1
    } while overlap && chars.count > 0
    
    return (chars.count == 0 ? 1 : 0)
}

func checkOverlap(_ c: [Character]) -> (Bool, [Character]) {
    var chars = c // 중복 요소 제거를 위해 상수인 c를 변수 chars로 복사
    var overlap = false
    
    for i in 0..<chars.count-1 {
        if chars[i] == chars[i+1] {
            chars.remove(at: i+1)
            chars.remove(at: i)
            overlap = true
            break
        }
    }
    
    return (overlap, chars) // 튜플 반환
}

가장 처음 시도한 방법. 평소대로 하지 않고 나름 색다른 방법을 써보겠다고 튜플이며 함수를 따로 떼어내는 등의 시도를 했지만, 모두 헛짓거리로 판명남 🙃 정답은 맞는 거 같은데 꽤 많은 테스트 케이스에서 시간 초과 가 떠버림. 스스로 생각해봤을 때

1. checkOverlap 함수 속 chars.remove에서 특정 인덱스 요소를 삭제하는 데 효율성이 떨어지고
2. 매번 배열의 0번부터 중복을 찾는 것도 비효율적이고
3. 무엇보다도 잘 안 쓰던 튜플 써본다고 광고하듯이 반복문 안에서 overlap과 chars를 저따위로 두 번이나 호출한 것

이 세 가지가 실패 요인이 아니었을까 싶다. (아마 3번을 개선해도 시간 초과라는 결과는 변함없을 듯)

 

 

# 풀이 2
for문 안 인덱스 조절해가며 요소 제거하기

import Foundation

func solution(_ s: String) -> Int{
    var chars = [Character]()
    
    s.forEach { // String을 [Character]로 변환
        chars.append($0)
    }
    
    var i = 0
    
    while i < chars.count-1 {
        if chars[i] == chars[i+1] {
            chars.remove(at: i+1)
            chars.remove(at: i)
            if chars.count < 2 {
                break // 배열의 크기가 2 미만이면 중복 확인의 의미X
            }
            if i > 0 {
                i -= 1 // 요소 2개를 제거했으니 인덱스를 전으로 돌림
            }
        } else {
            i += 1
        }
    }
    
    return (chars.count == 0 ? 1 : 0)
}

따로 떼어낸 함수를 사용하려는 헛짓거리를 관두고 익숙한 방법으로 돌아감. 이번에도 정답인 듯 했으나, 마찬가지로 테스트 케이스에서 절반 이상이 시간 초과가 나왔다.

 

 

# 풀이 3
드디어 생각난 Stack

import Foundation

func solution(_ s: String) -> Int{
    var str = s[s.startIndex]
    var chars = [str]

    for i in 1..<s.count {
        str = s[s.index(s.startIndex, offsetBy: i)]
        if chars.last == str {
            chars.removeLast()
        } else {
            chars.append(str)
        }
    }

    return (chars.isEmpty ? 1 : 0)
}

겨우 세 번째 시도가 되어서야 스택이 생각났다. 순차적으로 문자를 살펴본다고 생각하지 말고 새 배열에 문자를 하나씩 차곡차곡 넣는다고 생각하면 쉽게 풀릴 문제였는데... 지금 생각해보면 아주 간단한 문젠데 왜 당시엔 떠오르지 않았는지... 🤦

그런데 당연히 스택을 썼으니 통과할 거라는 예상과 달리, 이번 풀이도 앞의 두 개와 마찬가지로 시간 초과가 떴다...! 대체? 왜??🤷 방법은 이것뿐이라는 생각에 도대체 어디서 시간을 그렇게 잡아먹었는지 뒤져봤고, 앞 두 풀이와 달리 이번 풀이에서 사용하지 않은 게 하나 있었다.

 

 

# 풀이 4
해답은 String 대신 [Character]

import Foundation

func solution(_ s: String) -> Int{
    var chars = [Character]()
    var result = [Character]()
    
    s.forEach { // String을 [Character]로 변환
        chars.append($0)
    }
    
    for c in chars {
        if result.isEmpty {
            result.append(c)
        } else {
            if result.last == c {
                result.removeLast()
            } else {
                result.append(c)
            }
        }
    }

    return (result.isEmpty ? 1 : 0)
}

이번 풀이는 풀이3과 거의 비슷하다. 단 하나, String을 [Character]로 변환했다는 것만 빼면.

나는 어차피 스택을 사용할 거면 굳이 [Character]를 사용해서 불필요한 메모리를 늘리고 String을 한 바퀴 돌려 배열을 채우는 게 더 비효율적이라고 생각해서 풀이 3에서는 String을 그대로 사용하고 문자열 인덱스를 통해 해당 인덱스의 문자를 불러오는 방법을 사용했다.

하지만 놀랍게도 이번 풀이는 시간 초과 없이 통과.

스위프트의 문자열 사용법을 익히려고 굳이 스트링을 사용한게 오히려 패착이 됐다. 스트링의 인덱스를 사용하는 것보다 차라리 캐릭터 배열로 변환하고 해당 배열을 사용하는 게 더 효율적이었다.