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

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

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

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "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는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

출처 : 프로그래머스

입출력 예에 대한 설명

입출력 예 #1

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

입출력 예 #2

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

입출력 예 #3

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

입출력 예 #4

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

입출력 예 #5

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

 

 

---

 

문제 이해

 

 

프로그래머스는 문제를 이해하는 데 많은 정보를 제공하기 때문에 예제를 꼼꼼히 읽으면 어떤 말인지 감은 온다.

하지만 이 문제 같은 경우에는 막상 구현하려고 보니 어라..? 왜 안되지? 라는 말을 수없이 되뇌었다.

하다 못해 다른 사람의 풀이를 참조하려고 했지만 substring을 대부분 사용하고 있었고, 풀이가 워낙에 다양했기 때문에

나만의 풀이 방법을 꼭 찾고 싶었다.

 

먼저 간단히 전체 로직을 아우르는 방법은 다음과 같다.

 

 

 

 

내가 압축하고자 하는 길이를 1부터 n(문자열 길이) 까지 다 바라보고 차례대로 압축해서 가장 짧은 길이를 찾는 것이다.

위의 그림에서는 압축하는 범위가 3일 때,

str = abc 이고 sub = abc 이다.

만약 같다면 2abc로 줄어들 것이고, 다르다면 str은 sub을 저장하고 sub은 다음의 "ded"를 저장할 것이다.

 

 

 

 

접근 방법

 

 

나는 최대한 이 문제를 직관적이면서도 간단하게 풀려고 노력해봤다.

문제 이해를 토대로 전체 로직을 상세히 풀어나가면 다음과 같다.

 

 

 

1. 문자열을 압축 단계를 위한 변수 하나를 설정한다. (level = 1)

 

 

2. while문으로 level <= size(문자열의 길이) 까지 반복을 실행한다.

 

 

3. 처음 부분 문자열은 0부터 level 까지를 저장한다. (str = s.substring(0, level))

 

 

4. 현재 부분 문자열과 다음 부분 문자열이 같을 경우,

- 2개 이상부터이므로 cnt 변수를 2로 초기화한다.

- cnt를 포함한 부분 문자열을 임시로 저장하는 temp를 빈 문자열로 초기화해둔다.

- 이를 인지하는 boolean 함수를 설정한다.

문자열을 저장할 때 String 연산의 += 보다 효율이 좋은 StringBuilder를 선언한다.

 

 

5. 현재 부분 문자열(str)과 다음 부분 문자열(sub)을 비교할 것인데,

str은 0부터 level까지므로, sub는 j부터 j+level로 둔다. (j = level)

이 때, sub는 j + level 까지 담기 때문에 while문의 조건 범위는 j + level <= size 가 되어야 IndexOutOfBoundsException을 피할 수 있다.

 

 

 

6. str == sub 라면

 

- isChange를 true로 둔다.

- temp에 cnt + str 를 담는다.

- 그리고 cnt를 1 증가시킨다.

 

 

str != sub 라면

 

- isChange가 true일 경우, temp에 cnt + str이 저장돼있으므로 이를 sb에 덧붙인다.

- isChange가 false일 경우, 변화가 없었으므로 str을 sb에 덧붙인다.

 

다시 isChange를 false로 초기화한다.

 

str = sub 로 할당해서 다음 부분 문자열을 현재 부분 문자열로 바라보게 한다. 그래야 while문 초기로 돌아왔을 때 sub는 그 다음 부분 문자열을 가리키니 말이다.

temp와 cnt를 각각 빈 문자열과 2로 다시 초기화한다.

 

 

 

7. j += level 을 시킨다.

 

 

8. 부분 문자열들을 비교하는 while문이 끝났을 경우, temp의 저장 유무에 따라 결과가 정해진다.

temp가 비어있다면 마지막에 아직 덧붙이지 않은 문자열이 존재할 것이므로 j-level ~ size 만큼 sb에 덧붙인다.

 

 

 

 

temp가 존재한다면 temp와 j ~ size 만큼 sb에 덧붙인다.

 

 

 

 

9. 가장 짦은 길이를 구해야 하기 때문에 최소를 담기 위한 변수 min 와 sb 의 길이를 비교해서 작은 것을 min에 담는다.

(min = s.length로 초기화. 초기값으로 최댓값을 지정해야 최소를 찾을 수 있기 때문) 

 

 

 

질문하기 탭에 자주 보이는 답변으로 cnt가 10이상일 경우 이를 문자열로 받아들이기 때문에 2개인 점을 유의하라는 말이 많이 보인다.

혹시나 이를 놓쳤다면 한번 더 본인의 코드를 살펴보는게 좋을 것 같다.

 

테스트 케이스 : aaaaaaaaaab
출력 : 4

10ab

 

 

전체 코드

 

fun solution(s: String): Int {
    var level = 1
    val size = s.length
    var min = s.length

    while (level <= size) {
        var str = s.substring(0, level)
        var isChange = false
        val sb = StringBuilder()
        var cnt = 2
        var temp = ""

        var j = level
        while (j + level <= size) {
            val sub = s.substring(j, j + level)
            if (str == sub) {
                isChange = true
                temp = cnt.toString() + str
                cnt++
            } else {
                sb.append(if(isChange) temp else str)
                isChange = false
                str = sub
                cnt = 2
                temp = ""
               
            }
            j += level
        }
        sb.append(if(temp.isEmpty()) s.substring(j-level, size) else temp + s.substring(j,size))
        min = minOf(min, sb.length)
        level++
    }
    return min
}