문자열 압축

LEEHAKJIN-VV·2022년 5월 26일

프로그래머스

목록 보기

12/37

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한 사항

s의 길이는 1 이상 1,000 이하입니다.
s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s	result
"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

입출력 예 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

내가 제출한 코드

import Foundation

func solution(_ s:String) -> Int {
    var curStr: String = "" // 현재 자른 문자열
    var result: Int = s.count // 압축된 문자열 중 가장 짧은 길이
     
    for i in stride(from:s.count / 2, to:0, by:-1) { //2 ~ N/2반복
        var count = i // 문자열에서 자르고자 하는 인덱스 시작범위
        var zipStr: String = "" // 압축된 문자열
        var zipCount = 1 // 문자열 내에서 각 문자가 압축된 횟수
  
        let lastIndex = s.index(s.startIndex, offsetBy:i) // 제일처음 문자열의 마지막인덱스
        var preStr: String = String(s[s.startIndex..<lastIndex]) // 이전 문자열 (초깃값은 [0 ~ 자르는 문자 단위]

        while count < s.count {      
            let startIndex = s.index(s.startIndex, offsetBy: count)
            let endIndex = s.index(s.startIndex, offsetBy: count+i, limitedBy: s.endIndex) ?? s.endIndex
            curStr = String(s[startIndex..<endIndex]) // 문자열 자름
            
            if preStr == curStr { // 압축하는 경우
                zipCount += 1
            } else { // 압축하지 않는 경우
                if zipCount != 1 { // 같은 값이 연속하지 않는 경우 1을 생략하기 위한 조건
                    zipStr.append("\(zipCount)")
                    zipCount = 1
                }
                zipStr.append(preStr)
                preStr = curStr
            }
            count += i
        }
        zipResult(zipStr, &result, zipCount, curStr) // 압축된 문자열 결과 비교
    }
    
    return result
}

func zipResult(_ zipStr: String, _ min: inout Int, _ zipCount: Int, _ curStr: String){
	var resultStr: String = zipStr
    if zipCount != 1 {
        resultStr.append("\(zipCount)")
    }
    resultStr.append(curStr)
    
    if resultStr.count < min {
        min = resultStr.count
    }
}

코드 설명

입력으로 들어온 문자열을 압축해야 하는 문제다. 예를 들어 입력으로 들어온 문자열의 길이가 N이라고 가정하자. 압축을 하기 위해선 1,2,3... N/2 경우에서만 압축하면 된다. N/2 보다 큰 경우는 압축이 되지 않기 때문이다.

이를 기반으로 코드를 작성하면, 우선 범위 1,2,3... N/2 중 가장 짧은 문자열을 찾기 위해 모든 경우를 압축해야 한다. 잘라야 하는 문자의 단위를 for loop를 이용하여 표현하였고, 각 단위마다 문자열 압축은 while 문을 이용하였다.

우선 주로 사용되는 프로퍼티들을 소개한다.

preStr: 문자열에서 이전에 자른 문자열
curStr: 현재 자른 문자열
zipStr: 각 case마다 압축된 문자열
zipCount: 문자열 내에서 동일한 문자가 나타난 횟수

다음으로 코드를 살펴보겠다.

우선 이전 문자열의 초깃값은 입력된 문자열에서 [0~자르는 문자 단위]의 범위만큼 자른 문자열이다. 문자열을 자르는 방법은 우선 자르고자 하는 시작 인덱스와 마지막 인덱스를 구하고 이를 subscript에 넣어주어 자른 문자열을 구한다. 반환 타입이 Substring 타입이므로 형 변환을 사용해야 한다. 인덱스를 구하는 방법은 String 타입의 인스턴스 메소드 index를 사용한다.

let lastIndex = s.index(s.startIndex, offsetBy:i) // 제일처음 문자열의 마지막인덱스
var preStr: String = String(s[s.startIndex..<lastIndex]) // 이전 문자열 (초깃값은 [0 ~ 자르는 문자 단위]

다음으로 문자를 실제로 자르는 코드를 살펴본다. 현재 자른 문자열을 얻기 위해, 이전 문자열과 마찬가지로 index 메소드를 사용하였다. 이전 문자열과 현재 읽은 문자열의 값이 같다면 이는 연속되는 문자열이다. 그러므로 압축을 진행한다. 이때 연속되는 횟수를 저장해야 하기 때문에 프로퍼티 zipCount 값을 1 증가 시킨다. 두 문자열이 같지 않으면 압축이 되지 않는다. 그러므로 압축 문자열에 이전 문자열의 값을 그대로 복사한다. 그리고 현재 문자열과 다음에 읽는 문자열을 비교하기 위해 이전 문자열에 현재 문자열의 값을 할당한다. preStr = curStr 이 과정을 문자열 끝까지 읽으면 while 문을 탈출한다.

while count < s.count {
    let startIndex = s.index(s.startIndex, offsetBy: count)
    let endIndex = s.index(s.startIndex, offsetBy: count+i, limitedBy: s.endIndex) ?? s.endIndex
    curStr = String(s[startIndex..<endIndex]) // 문자열 자름
    
    if preStr == curStr { // 압축하는 경우
        zipCount += 1
    } else { // 압축하지 않는 경우
        if zipCount != 1 { // 같은 값이 연속하지 않는 경우 1을 생략하기 위한 조건
            zipStr.append("\(zipCount)")
            zipCount = 1
        }
        zipStr.append(preStr)
        preStr = curStr
    }
    count += i
}

while 문을 탈출한 후 압축된 문자열에 남은 문자열을 값을 할당해야 한다. 그리고 각 case마다 압축된 문자열의 길이를 비교한다. 이를 수행할 함수로 zipResult를 구현하였다. 각 압축된 문자열마다 가장 짧은 경우의 길이는 min 프로퍼티에 저장하였다.

func zipResult(_ zipStr: String, _ min: inout Int, _ zipCount: Int, _ curStr: String){
	var resultStr: String = zipStr
    if zipCount != 1 {
        resultStr.append("\(zipCount)")
    }
    resultStr.append(curStr)
    
    if resultStr.count < min {
        min = resultStr.count
    }
}

몰랐던 사실 or 기억하면 도움이 될 만한 사실

Swift의 String.index

Declaration

@frozen struct Index

Swift에서 문자열 자르기는 다른 언어보다 수행할 작업이 조금 더 많은 것 같다. 우선 Int값으로 인덱스를 접근할 수 없고 String.index 타입으로 접근해야 한다. 이 타입은 인덱스 접근을 위한 특수한 형태인 구조체로 구현되어 있다. 다른 언어는 Int 타입으로 접근하는데 왜 Swift에서는 굳이 이 타입을 사용하는 것인가?

그래서 검색을 진행하였다. stackoverflow의 댓글에서 찾은 내용이다. (링크)

Why is String.Index needed?
It would be much easier to use an Int index for Strings. The reason that you have to create a new String.Index for every String is that Characters in Swift are not all the same length under the hood. A single Swift Character might be composed of one, two, or even more Unicode code points. Thus each unique String must calculate the indexes of its Characters. It is possible to hide this complexity behind an Int index extension, but I am reluctant to do so. It is good to be reminded of what is actually happening.

대충 번역을 해보자면 String.index가 필요한 이유는 Swift에서는 각 문자가 하나 또는 여러 개의 유니코드로 구성된다. 즉 1개의 문자는 사실 같은 길이가 아닌 것이다.(각 문자마다 사용되는 유니코드가 다르고, 그 유니코드도 각자 길이가 다르므로) 그러므로 Int형으로 통일되게 접근하지 말고, 각 문자열 내에서 고유의 위치(인덱스)를 찾아 접근해야 한다. 이제 이유를 알았으니 귀찮아도 String.index 타입을 이용하여 부분 문자열을 구하자..

그리고 위 코드에서 다음과 같이 index메소드에서 limtedBy 인자를 사용한 것을 확인할 수 있다.

Declaration

func index(_ i: String.Index, offsetBy n: String.IndexDistance, limitedBy limit: String.Index) -> String.Index?

let endIndex = s.index(s.startIndex, offsetBy: count+i, limitedBy: s.endIndex) ?? s.endIndex

limtedBy는 만약 offsetBy에 할당된 Int 값이 limitedBy에 할당된 값보다 크다면 nil을 반환한다. 즉 위 코드에서는 limitedBy에 문자열의 끝 인덱스의 값을 할당했기 때문에 이를 넘어서는 값은 nil을 반환한다. 그러나 현재 경우에는 nil 병합 연산자를 사용하여 nil 대신 endIndex 프로퍼티에 문자열 s의 마지막 인덱스를 할당하게 끔 구현하였다.

LEEHAKJIN-VV

이전 포스트

k진수에서 소수 개수 구하기

다음 포스트