[프로그래머스] 2020 Kakao Blind Recruitment - 문자열 압축

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

 

입력 & 출력

문제는 링크에서 확인 바랍니다

풀이

1개의 문자열을 찾을 경우를 생각해보자
첫번째 문자 기준 n개의 문자열과 그 후의 n개 문자열이 같다면 이를 줄여 n문자열로 만들어야한다
재귀를 활용해 다음 문자열로 넘기도록 만들면 간단하게 처리할 수 있다

1개의 문자열로 압축하는 것이 최소라는 보장이 없으니, 전체 문자열 크기만큼 반복한다
그러나 압축할 수 있는 최대 크기는 전체 크기의 반이기에 문자열 크기 반만큼만 반복한다

현재 문자열과 다음 문자열이 같을 경우, repeating 변수에 1을 더해주고
현재 문자열과 다음 문자열이 같지 않을 경우 repeating과 현재 문자열을 넣어준다
만일 repeating이 1이라면 (초기값이 1) 현재 문자열만 넣어준다

위 과정을 문자열 끝까지 반복한다

현재 문자열과 찾는 범위 문자열이 전체 문자열 수를 넘어섰을 때
범위를 더하는 대신 현재 문자열부터 마지막 문자열까지를 넣어준다 

 

Swift 전체 코드

var complete = false
var result = ""
var repeating = 1
var min = s.count

func recursion(_ now: Int, _ range: Int) {
    let startRange = s.index(s.startIndex, offsetBy: now)
    let nowRange = s.index(startRange, offsetBy: range)
    
    if now + range + range <= s.count {
        let nextRange = s.index(nowRange, offsetBy: range)
        let nowString = s[startRange..<nowRange]
        let nextString = s[nowRange..<nextRange]
        
        if nowString == nextString {
            repeating += 1
        } else {
            if repeating != 1 {
                result.append("\(repeating)")
            }
            result.append("\(nowString)")
            repeating = 1
        }
        recursion(now + range , range)
    }
    
    if !complete && now + range <= s.count && now + range + range >= s.count {
        complete = true
        if repeating != 1 {
            result.append("\(repeating)")
        }
        result.append("\(s[startRange...])")
    }
}

for j in 1...s.count / 2{
    recursion(0, j)
    
    if min > result.count {
        min = result.count
    }
    
    result = ""
    repeating = 1
    complete = false
}

return min