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

문제

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

 

코드

import Foundation

func solution(_ s:String) -> Int {
    let N = s.map { String($0) }
    if N.count == 1 {
        return 1
    }
    var array = [N.count] //맨 처음 비교대상은 한번도 압축이 되지 않을때, 즉 문자열 자체의 길이
    var answer = ""
    var prev = ""
    var count = 1
        
    for step in 1...N.count/2 { //최대로 압축할 수 있는 범위가 문자열 절반의 길이
        answer = ""
        prev = N[0..<step].joined()
        count = 1
        for j in stride(from:step, to:N.count, by: step){
            var idx = j + step
            if j + step > N.count - 1{
                idx = N.endIndex
            }
            if prev == N[j..<idx].joined() {
                count += 1
            }
            else{
                if count == 1 {
                    answer += prev
                }
                else{
                    answer += String(count)+prev
                }
                prev = N[j..<idx].joined()
                count = 1
            }
        }
        if count == 1 {
            answer += prev
        }
        else{
            answer += String(count)+prev
        }
        array.append(answer.count)
    }
    
    return array.min()!
}

 

풀이

1) 문제를 이해해보면, 차례대로 길이 1부터 시작해서 잘라서 이어붙인 문자열의 길이가 최소인 값을 return하는 문제이다.

예를들어 ababcdcdababcdcd 라는 문자열이 있다고 생각했을 때,

1개 단위로 자르기 -> ababcdcdababcdcd (16)

2개 단위로 자르기 -> 2ab2cd2ab2cd (12)

8개 단위로 자르기 -> 2ababcdcd (9)

여기서는 2ababcdcd가 최소이다.

이때 주의할 점은 1개 단위로 자른다고 했으면 반드시 차례대로 1씩 잘라야하고, 중간에 자르는 갯수가 바뀔 수 없다.

 

2) 여기서 규칙을 발견할 수 있는것은 최대값은 1개씩 잘랐을 때, 즉 문자열 길이 그대로일 것이고

자를 수 있는 길이는 최대 문자열 길이의 절반 만큼일 것이다.

따라서 필자는 나올 수 있는 모든 길이를 다 array에 넣어두고 비교하기 위해, 맨 처음 문자열의 길이 (1개씩 잘랐을 때의 길이)가 있는 array를 초기화하고, 문자열의 길이 절반까지 만큼 잘랐을 때 각각의 길이를 비교하기 위해 아래와 같은 반복문을 세웠다.

func solution(_ s:String) -> Int {
    let N = s.map { String($0) }
    
    var array = [N.count] //맨 처음 비교대상은 한번도 압축이 되지 않을때, 즉 문자열 자체의 길이
        
    for step in 1...N.count/2 { //최대로 압축할 수 있는 범위가 문자열 절반의 길이

 

(아래는 틀린 풀이임)

3) 그 다음, 맨 첫번째부터 각 길이만큼 문자열을 자르면서 이를 그 다음 스텝부터 비교했다.

앞에서 자른 문자열이 그 다음 문자열과 같다면 count를 계속 1씩 증가시켰고, 맞지않게 되는 시점에 count가 1이 아닐 경우에는 그 문자열의 갯수와 문자열, count가 1이면 문자열을 추가하게 해주었다. (문제 조건에서 1은 생략하라고 나와있음)

그리고 반복문을 벗어났을 때, 남은 문자열을 처리하지 못하므로 남은 문자열을 answer에 더해주고, 최종적인 answer의 count를 array에 추가한 뒤, 마지막에 array의 최소값을 return하도록 했다.

 import Foundation

func solution(_ s:String) -> Int {
    let N = s.map { String($0) }
    if N.count == 1 {
        return 1
    }
    var array = [N.count] //맨 처음 비교대상은 한번도 압축이 되지 않을때, 즉 문자열 자체의 길이
    var answer = ""
    var prev = ""
    var count = 1
    var end = 0
        
    for step in 1...N.count/2 { //최대로 압축할 수 있는 범위가 문자열 절반의 길이
        answer = ""
        prev = N[0..<step].joined()
        count = 1
        for j in stride(from:step, to:N.count-step, by: step){
            if prev == N[j..<j+step].joined() {
                count += 1
            }
            else{
                if count == 1 {
                    answer += prev
                }
                else{
                    answer += String(count)+prev
                }
                prev = N[j..<j+step].joined()
                count = 1
            }
        }
        if count == 1 {
            answer += prev
        }
        else{
            answer += String(count)+prev
        }
    }
    
    return array.min()!
}

그런데, 테스트 결과 5개 중 1개만 맞는 결과가 나왔다.

 

범위가 어디서 잘못되었는지 고민하다가 이 부분이 잘못되었음을 깨달았다.

압축이 되지 않는 맨 마지막 문자열을 처리하기 위해 for문의 마지막을 N.count-step으로 잡았으나 

예를들어 abcabcdefdef 와 같은 문자열에서 3개 단위로 압축할 때를 생각해보면 N.count-step은 9이므로, 9번째 인덱스부터 그 뒤인 문자열인 def를 앞의 def와 비교할 수 없게된다. 따라서 이와같은 경우에는 def 또한 압축할 수 있음에도 압축하지 못해 상이한 값이 나왔던 것이다.

따라서 문자열 끝까지 판별하기 위하여 조건을 조금 바꾸었다.

 

1) 반복문의 범위를 우선 문자열의 끝까지로 변경하고 (N.count-step -> N.count)

2) 만약 현재의 prev 그 다음 대상이 문자열의 끝을 포함하는 경우, 인덱스를 끝 인덱스로 주어서 문자열 끝까지 비교할 수 있도록 수정했다.

        for j in stride(from:step, to:N.count, by: step){
            var idx = j + step
            if j + step > N.count - 1{
                idx = N.endIndex
            }

 

위와같이 수정하면, 문자열 끝까지 prev와 비교할 수 있게되고, 끝까지 비교했을 때 서로 같다면 count+=1을 하여 반복문을 빠져나와 answer에 추가할 수 있게되고, 같지않다면 그냥 추가하는 방식으로 수정된다.

        if count == 1 {
            answer += prev
        }
        else{
            answer += String(count)+prev
        }
        array.append(answer.count)

 

그리고 여기서 마지막에 return array.min()! 으로 최소값을 구하면 짧은 길이를 구할 수 있음

 

상당히 시간도 많이들고 어려운 문제였다. 나중에 꼭 다시 풀어봐야할듯.

 

혹시 틀린 부분이 있다면 댓글 주시면 감사하겠습니다 :)