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

✅ 이번 시간에는 프로그래머스 문제 알아보자.

 

https://programmers.co.kr/learn/courses/30/lessons/60057

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

 

🟠 풀이는 이것이 코딩테스트다 - 파이썬 이 책 참고함.

 

내가 이 문제가 엄청 어려웠던 이유가 있는데, 내가 문제를 꼼꼼하게 읽지 않는다는 점.

예를 들면,

나는 "abbcbbc" 라는 문자열이 존재할 경우

"a2bbc"로 압축되어서 길이가 5가 나오는 것이 최적의 압축 방법이자 정답이라고 생각했으나,

문제에서는 "abbcbbc"로 답이 7이 나와야 한다고 한다.

즉, 무슨 말이냐면, 3자리씩 검사한다고 가정했을 때, abb 를 검사하고 맞지 않으면, index 1자리부터 bbc를 검사하는 것이 아니라는 말이며, "abb" 3자리를 검사했으면 무조건 3자리를 점프해서 "cbb"를 검사한다는 말이였다.

 

이에 대한 설명를 입출력 예제 #5 해석 부분에 문제에 적혀져 있다.

(이 부분을 읽지 못해서, 이게 레벨 2가 맞아..? 이러면서 일주일동안 헤매었다...)

 

코드에 대한 설명은 주석으로 달아 두었다

 

//
//  main.swift
//  algorithm
//
//  Created by Hamlit Jason on 2021/11/04.
//

/*
 https://programmers.co.kr/learn/courses/30/lessons/60057
 */

import Foundation

func solution(_ s:String) -> Int {
    
    var answer = s.count // s의 길이
    
    // 1. 한개부터 압축 단위를 늘려가면서 확인한다.
    for step in stride(from: 1, to: s.count / 2 + 1, by: 1) {
        //print(step) // step은 1,2,3 ...
        
        var compressed = ""
        
        var stepIndex = s.index(s.startIndex, offsetBy: step)
        var prev = s[..<stepIndex] // 앞에서부터 step만큼의 문자열 추출
        var count = 1
        
        //print(prev)
        
        
        // 2. step 단위 크기 만큼 증가시키며 이전 문자열과 비교
        for j in stride(from: step, to: s.count, by: step) {
            // stride to는 이하, through는 미만
            //print("j is \(j)")
            
            var vstep = step // 인덱스 초과 방지
            
            if (j+step) > s.count { // 문자열 길이 8, step 3, j 6인 경우 vstep 2로 조정
                //print("s count \(s.count)")
                vstep = s.count - j // 남은 문자열 길이만큼 prev로 만들기
            }
            
            var first = s.index(s.startIndex, offsetBy: j)
            var last = s.index(s.startIndex, offsetBy: j+vstep)
            
            if prev == s[first..<last] {
                // 이전 상태와 동일하다면
                count = count + 1
            } else {
                // 다른 문자열이 나와 더이상 압축하지 못하는 경우라면,
                if count >= 2 {
                    compressed = "\(compressed)\(count)\(prev)"
                } else {
                    compressed = "\(compressed)\(prev)"
                }
                
                // 다시 초기화 상태로 - 이전 상태와 다른 다음 문자열음 prev에 넣어주기
                prev = s[first..<last]
                count = 1
            }
        }
        
        // 3. 남아 있는 문자열에 대해서 정리
        if count >= 2 {
            compressed = "\(compressed)\(count)\(prev)"
        } else {
            compressed = "\(compressed)\(prev)"
        }
        
        
        // 만들어지는 압축 문자열이 가장 짧은 것이 정답
        //print("answer choice \(answer) \(compressed.count) : \(compressed)")
        answer = min(answer, compressed.count)
    }
    
    
    return answer
}

print(solution("abbcbbc")) // 8자리