[Swift 알고리즘] 프로그래머스(Lv.2) - 문자열 압축 / 2020 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 문자열 압축" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 문자열 압축

 

---

풀이

이번 문제는 문자열 처리 문제입니다.

프로그래머스 2레벨에서 벽을 느껴 백준에서 문제 좀 풀다 오랜만에 2레벨 문제를 풀어보았습니다.

 

겁 먹었다

이번 문제를 풀면서 느낀 점은 지레 겁먹지 말자는 것입니다.

문제의 해답 알고리즘을 처음부터 생각했는데 괜히 아닐 거 같아서 더 길게 고민했습니다.

 

아니라고 생각한 이유는 시간복잡도 제한이 확실하지 않았기 때문에... 불안한 마음이 컸던 것 같네요.

결국에는 input length의 절반까지만 반복문을 돌려도 되기 때문에 아무 문제가 없습니다.

 

문제 풀이

자르는 단위는 문자열의 절반 길이까지만 가능합니다.

따라서 1부터 s.count/2까지 반복을 해줍니다.

 

자르는 단위에 따라 입력되는 문자열을 잘라 배열로 만들어 줍니다.

예를 들어 apple이라는 문자열을 2글자 단위로 자른다고 하면 "ap", "pl", "e"가 되는 것이죠.

 

잘라진 문자열 중 같은 문자열이 연속적으로 나오면 압축을 하고 아니라면 이어 붙여줍니다.

 

1부터 s.count/2까지 반복하며 압축된 문자열의 최소 길이를 구해주면 됩니다.

 

한 가지 더 생각해야 할 점은 input 제한이 1 이상이라는 것인데요.

한 글자인 경우 s.count/2에서 런타임 에러가 발생하게 됩니다. 따라서 길이가 2 이하인 문자열은 압축을 해도 길이가 동일하기 때문에 조건 처리를 해줘야 합니다.

 

---

전체 코드

import Foundation

func solution(_ s:String) -> Int {
    if s.count <= 2 {
        return s.count
    }
    
    var result: Int = 0
    for unit in (1...(s.count/2)) { //자르는 단위
        // print("--- \(unit) ---")
        let slicingStrings = slicing(str: s, unit: unit)
        let compressingString = compress(slicingStrings)
        
        result = (result > 0) ? min(result, compressingString.count) : compressingString.count
    }
    
    return result
}

func slicing(str: String, unit: Int) -> [String] {
    
    let strings = Array(str)
    let length = strings.count
    
    var words: [String] = []
    for i in stride(from: unit-1, to: length, by: unit) {
        let word = strings[(i-unit+1)...i].map{ String($0) }.joined()
        words.append(word)
    }
    
    if length % unit > 0 {
        words.append(String(strings[(length - length%unit)...]))
    }
    
    // print("words: \(words)")
    return words
}

func compress(_ strings: [String]) -> String {
    let length = strings.count
    var string = ""
    var count = 1
    for i in 0..<(length-1) {
        if strings[i] == strings[i+1] {
            count += 1
        } else {
            let addString = (count > 1) ? ("\(count)\(strings[i])") : ("\(strings[i])")
            string += addString
            
            count = 1
        }
    }
    
    let addString = (count > 1) ? ("\(count)\(strings[length-1])") : ("\(strings[length-1])")
    string += addString
    
    // print("compress: \(string)")
    return string
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.