[Algorithm] 문자열 압축

🖥 문제

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

🤔 풀이 방법

1. 변수
   • s: [String] : 압축할 문자열
   • compressedS: [String] : 압축된 문자열 중 가장 짧은 문자열
   • start: Int : 비교의 기준이 되는 문자열의 시작 인덱스
   • current: Int : 비교중인 인덱스
   • num: Int : 압축이 가능한 개수
   • tmp: [string] : 압축된 문자열
2. for i in 1...s.count/2 + 1 {}
   • 1개 ~ s.count/2개의 문자열 단위로 압축하기 위하여 반복한다.
3. while current+i-1 < s.count && s[start...start+i-1] == s[current...current+i-1] {}
   • 비교의 기준이 되는 문자열과 나머지 문자열을 비교한다.
   • 문자열이 연속되면 연속되는 횟수만큼 num을 +1 해준다.
4. 2번 이상 반복될 경우, 즉 num이 2 이상일 경우
   • tmp.append(String(num))
   • tmp.append(contentsOf: s[start...start+i-1])
   • num과 기준 문자열을 넣어 압축한다.
5. tmp.append(contentsOf: s[start...start+i-1])
   • 압축이 되지 않을 경우 기준 문자열만 넣는다.
6. 모든 비교가 끝나고 남은 문자열을 넣는다.

7. compressedS = tmp == [] || compressedS.count < tmp.count ? compressedS : tmp
   • compressedS와 tmp를 비교하여 가장 짧은 문자열을 compressedS에 넣는다.
8. return compressedS.map{$0}.reduce("", +).count
   • 모든 과정이 끝나면 compressedS의 문자열 길이를 리턴한다.

👩🏻‍💻 Swift Code

import Foundation

func solution(_ s:String) -> Int {
    let s = s.map{String($0)}
    var compressedS = s

    // 1 ~ s.count/2 개의 문자열 단위
    for i in 1...s.count/2 + 1 {
        var start = 0
        var current = i
        var num = 1
        var tmp: [String] = []

        while current < s.count {
            // i개의 문자열 단위로 비교
            while current+i-1 < s.count && s[start...start+i-1] == s[current...current+i-1] {
                current += i
                num += 1
            }

            // 압축, 2이상 반복되면 반복된 횟수 추가
            if num > 1 {
                tmp.append(String(num))
                tmp.append(contentsOf: s[start...start+i-1])
            } else {
                tmp.append(contentsOf: s[start...start+i-1])
            }

            // 압축되지 않은 문자열을 추가
            if current >= s.count - i && current < s.count {
                while current < s.count {
                    tmp.append(s[current])
                    current += 1
                }
            }
            start = current
            current += i
            num = 1
        }
        compressedS = tmp == [] || compressedS.count < tmp.count ? compressedS : tmp
    }
    return compressedS.map{$0}.reduce("", +).count
}

 

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