[프로그래머스] 문자열 압축 (Swift)

https://programmers.co.kr/learn/courses/30/lessons/60057?language=swift

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

2020 카카오 블라인드 코딩테스트

알파벳소문자로 이루어진 문자열(1~1000자)이 주어지고

이를 맨앞에서부터 일정 단위만큼 잘라서 연속되며 + 중복되는 글자를 -> 연속적으로 중복되는 횟수 + 반복되는 문자열 로 압축할 수 있다고 할 때 가장 짧게 문자열을 압축할 수 있는 길이를 구하는 문제

 

설명이 좀 부족해서 예를 들어보면

aabbaccc -> 2a2ba3c 로 압축된다고 보면 된다.

2a == a가 2개가 연속적으로 반복된다는 뜻

 

중요한 점은 입출력 예시 설명에 있는데

이것이다. 제일 앞에서부터 정해진 길이만큼 잘라야 된다는 것!

 

접근방법

1. 정해진 길이 즉 문자열을 자르는 단위를 1부터 전체문자열길이/2 인 경우를 모두 구해서 비교해야한다.

(solution 함수의 for문 참고)

2. 자르는 단위를 len이라고 하면, 전체 문자열을 len 단위로 자른 부분 문자열들을 모두 배열에 담는다

(getSubStringsArray함수 참고)

즉, 문자열이 aabbaccc이고, len이 1인 경우이면

getSubStringsArray함수의 결과로 나온 배열은 [a,a,b,b,a,c,c,c] 이다.

이때 문자열이 단위로 딱 나누어떨어지지 않을 수 있다.

예를들어, aabbaccc에서 len이 3인 경우 [aab,bac,cc] 이렇게 마지막 부분 문자열은 3자리가 아니라 2자리인데 이것도 마지막 원소로 넣어서 배열을 반환해준다.

그리고 나서 배열에서 마지막 원소를 빼내서 remain(남은 문자열)에 저장해둔다.

그러면 배열에는 모두 단위길이만큼의 부분 문자열들이 담겨있다.

3. 이 배열을 앞에서부터 마지막 원소 전까지 탐색하며 문자열이 반복되는 횟수를 카운트 해준다. 그와 동시에 압축 문자열을 생성한다.

(getCompactString 함수 참고)

3-2. 만들어진 압축 문자열에 remain을 붙여 최종 압축 문자열을 반환한다.

4. 압축 문자열의 길이를 반환한다.

5. 누적된 최소 압축 길이와 비교하며 최소 압축 길이를 갱신해간다.

 

오답노트

테스트케이스 5에서 core dumped 오류가 발생했는데 이는 swift의 for 문 범위에 0...-1 같은 경우가 허용되지 않기 때문이다.

테스트케이스 5는 한자리 문자열이 s로 입력되었을 경우이다. (아마)

문자열이 한자리면 solution 함수에 있는 for 문의 범위인 1...1(문자열길이)/2 로 되서 core dumped가 발생했다.

따라서 문자열 길이가 2보다 작은 경우 압축하지않고 문자열 길이를 반환하면 통과된다.

너무 애드혹 같은 방법이긴 한데...그래서 단위를 1...문자열길이/2 에서 1...ceil(문자열길이/2)로 바꿨다.

이렇게 하면 마지막 단위 길이는 사실 하지 않아도 되는 경우인건데.. 뭐가 더 나은걸까

 

+ swift는 String이 값타입이라 그런지 Substring을 쓰기도 다른것보다 복잡하다

하지만 그렇게 복잡한건 아니니까..그래서 다들 String extension해서 푸셨더라

https://developer.apple.com/documentation/swift/substring

 

소스코드

import Foundation

func getSubStringsArray(_ len:Int, _ s:String) -> [String] {
    var remain:String = s
    var array:[String] = []
    while remain.count >= len {
        let lenIndex:String.Index = remain.index(remain.startIndex, offsetBy:len)
        array.append(String(remain[..<lenIndex]))
        remain = String(remain[lenIndex...])
    }
    
    array.append(remain)
    return array
}

func getCompactString(_ array:[String], _ remain:String) -> String {
    var compactStr = ""
    var repeatCnt:Int = 1
    for i in 0..<(array.count-1) {
        if array[i] == array[i+1] {
            repeatCnt += 1
        } else {
            if repeatCnt == 1 {
                compactStr += array[i]
            } else {
                compactStr += "\(repeatCnt)\(array[i])"
            }
            repeatCnt = 1
        }
    }
    
    if repeatCnt > 1 {
        compactStr += "\(repeatCnt)\(array.last ?? "")"
    } else if repeatCnt == 1 {
        compactStr += array.last ?? ""
    }
    
    compactStr += remain
    
    return compactStr
}

func getCompactLength(_ len:Int, _ s:String) -> Int {
    
    var array:[String] = getSubStringsArray(len, s)
    let remain:String = array.removeLast() ?? ""
    
    let compactStr:String = getCompactString(array, remain)
    
    return compactStr.count
}

func solution(_ s:String) -> Int {
    
    let lengthOfs = s.count
    
    var minOfCompactLength = lengthOfs
    
    /*
    if lengthOfs < 2 {
    	return lengthOfs
    }
    */
    
    for len in 1...Int(ceil(Double(lengthOfs)/2.0)) {
        let compactLength = getCompactLength(len, s)
        minOfCompactLength = minOfCompactLength > compactLength ? compactLength : minOfCompactLength
    }
    
    return minOfCompactLength
}