2020 KAKAO BLIND RECRUITMET - 문자열 압축, Swift

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

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

 

1. 기본적인 알고리즘은, 1칸씩 잘라보고, 그 다음 2칸씩 잘라보는 행위를 계속 반복하는 것이다.

이때 문자열이 1,000 자 라면 500자 까지만 잘라보면 되는데, 왜냐하면 501자를 자르게 되면 남은 길이가 499자 이므로 앞서 자른 문자와 무조건 일치하지 않는다. 따라서 전체길이 S 일 때  S/2 까지만 자르는 동작을 반복하면 된다.

2. 문자열의 길이가 1일때 예외처리

3. 문자열을 자를 때 자른 문자열이 이전 문자열과 일치 할 때, 나온 회수를 +1 해준다., 아니라면 배열에 추가한다.

4. 압축한 문자열 길이를 계산한다.

5. 자르는 범위 오른쪽 경계가 nil이거나 초과하면 반복문을 빠져나오고 다음 자르는 단위로 이동한다.

6. 반복된 회수가 1일때는 별도로 표시하지 않으므로 예외처리

 

연산 횟수는 최악의 경우 500 * 500 * 500 으로 125,000,000

 

 

 

import Foundation

final class CompressedString: CustomStringConvertible {
  let word: String
  var count: Int = 1

  init(word: String) {
    self.word = word
  }
  var countAnnotation: String {
    count > 1 ? String(count) : ""
  }

  var description: String {
    "\(countAnnotation)\(word)"
  }
}

func solution(_ s: String) -> Int {
  let wholeLenth = s as NSString
  let bound = wholeLenth.length / 2
  var shortestStringLenth = 1001
  if wholeLenth.length == 1 { return 1 }
  for unit in 0..<bound {

    var compressedStrings: [CompressedString] = []
    var lbound = s.startIndex
    var rbound = s.index(lbound, offsetBy: unit, limitedBy: s.index(before: s.endIndex))
    var previousString = CompressedString(word: "")
    while true {
      if rbound == nil || rbound! >= s.endIndex {
        let substring = CompressedString(word: String(s[lbound..<s.endIndex]))
        if !substring.word.isEmpty {
          compressedStrings.append(substring)
        }
        break
      }
      let substring = CompressedString(word: String(s[lbound...rbound!]))

      if substring.word == previousString.word {
        previousString.count += 1
      } else {
        compressedStrings.append(substring)
        previousString = substring
      }

      lbound = s.index(after: rbound!)
      rbound = s.index(lbound, offsetBy: unit, limitedBy: s.endIndex)
    }

    var legnth = 0
    compressedStrings.forEach {
      legnth += ($0.description as NSString).length
    }
    shortestStringLenth = min(shortestStringLenth, legnth)

  }
  return shortestStringLenth
}