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

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

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

 

문자열을 최소한으로 압축시킬 수 있을 때 까지 압축시켜보고 그 길이를 반환하는 문제. 

 

예를 들어 "aabbccd"의 경우 아래와 같은 과정을 거쳐 답을 얻어낼 수 있다. 

 

// string = "aabbccd"


# 1개씩 자를 때 
// a a b b c c d 
// a가 2개, b가 2개, c가 2개, d가 1개로 묶인다
// (1은 표기 X)
> 2a2b2cd

1개씩 자르는 경우를 먼저 봐보자. 결과를 먼저 보면 "2a2b2cd"이다. 중복되는 각 원소가 몇 번인지 세기 위해 cnt라는 변수에 값을 저장하면서 원소들을 비교해보자.

 

i	cur (=현재 원소)	cnt (=등장 횟수)
1	a	1
2	a	2
3	b	1
4	b	2
5	c	1
6	c	2
7	d	1

 

차례차례 봐보면, 현재 값과 다음에 올 값이 같으면 cnt가 증가하는 모습을 볼 수 있다. 

하지만 다음에 올 값과 다를 경우 cnt는 다시 1로 초기화되고 현재의 원소도 변경된다. 이 과정에서 우리는 이전의 요소들을 기억해줄 필요가 있다. 즉 cur이 b로 변하는 순간에 이전의 cur과 cnt를 기억해야한다는 것이다. 

 

다시 표로 이해해보자. 

i	cur (=현재 원소)	cnt (=등장 횟수)	result
1	a	1	-
2	a	2	-
3	b	1	2a
4	b	2	2a
5	c	1	2a2b
6	c	2	2a2b
7	d	1	2a2b2c
8	-	-	2a2b2cd

 

앞서 말했던 것 처럼, 원소가 바뀔때를 기준으로 이전 값들을 result에 추가하면 된다. 계속 반복하다보면 마지막의 경우는 어떻게 처리해야할까..? 

 

위 처럼 마지막(i = 7)에 cnt가 1일 경우에는 cur과 아직 cur에 저장되지 않은 나머지 string을 붙이면 된다 (뒤의 코드에서 설명) 

반면에 cnt가 1이 아닌 경우에는, 반복적인 원소가 등장하고 있다는 것이기에 cnt + cur + 나머지 string 을 추가해준다. 

계속 마지막 string을 추가해주는데 이 경우는 어떤 경우일까? 

 

만약에 위 string을 3개씩 끊어서 묶어본다고 생각해보자. 

 

i	string	cur (=현재 원소)	cnt (=등장 횟수)	result
1	"bccd"	aab	1	-
2	"d"	bcc	1	aab
3	-	-	-	aabbccd

 

전체 string에서 3개씩 끊어서 가져오기 때문에 위와 같은 프로세스를 거친다. 

i = 2일 때를 보면 string에 s가 남아있는 것을 볼 수 있다. 왜냐하면 3개씩 끊어가는데 남은 원소의 개수가 1개이기에 묶을 수가 없기 때문이다. 이러한 경우들을 잘 고려해서 코드로 구현해보면 아래와 같다. 

 

import Foundation

func solution(_ s:String) -> Int {
    // 문자의 최대 길이
    var result = 1000
    // 반으로 접는게 최대 축약
    var len = s.count / 2
    
    // 길이가 1일 경우 그냥 그대로 1 반환
    if s.count == 1 { return 1 }
    
    // 1개씩 묶는거부터 len개씩 묶는거까지
    for idx in 1...len {
        // string내 elements를 삭제할거라 변수 선언
        var s = s
        // 현재 묶음
        var cur = ""
        // 최종 묶음
        var res = ""
        // 현재 묶음의 등장 횟수
        var cnt = 1
        
        // idx개씩 묶으려는데, idx가 s.count(현재 원소)보다 크면 못묶음
        // > 나머지는 그냥 붙어야 함. 
        while s.count >= idx {
            // 묶음 범위 생성
            let range = s.startIndex..<s.index(s.startIndex, offsetBy: idx) 
            // 묶음
            var v = s[range]
            
            // 초기세팅
            if cur == "" {
                cur = String(v)
            // 같을 경우 cnt += 1
            } else if cur == String(v) {
                cnt += 1      
            // 다를 경우, 결과에 "추가하는 시점"
            } else { 
                if cnt == 1 {
                    res.append("\(cur)")
                } else { 
                    res.append("\(cnt)\(cur)")
                }
                // 현재값 & cnt 교체 
                cur = String(v)
                cnt = 1
            }
            // 현재 묶음 버리기 
            s.removeFirst(idx)
        }
        // 남은 cur과 s를 처리해준다. 
        // 1일 경우 중복없는 하나의 묶음으로서 남은 것 
        if cnt == 1 {
            res.append("\(cur)\(s)")
        // cnt가 1이 아닐 경우 중복된 묶음 + 나머지 값
        } else { 
            res.append("\(cnt)\(cur)\(s)")
        }
        
        // 결과 중 길이가 가장 짧은 값을 저장해두고 있어야 함
        if res.count < result { result = res.count}
    }
    return result
}

 

[ 프로세스 ]

 

* 위 설명으로 생략

---

문자열을 다루는데 조금 겁이 있었는데, 몇 번씩 계속 다루다 보니 점점 익숙해지는 느낌...! 

코드 구현도 구현이지만, 문제를 100% 이해하고 넘어가는게 중요하다고 한 번 더 깨달았다. 직접 케이스에 대해 하나하나 봐가면서 이해하니 완벽하게 예외 케이스까지 이해하게 된 기분이다. 문제를 마주하면 겁부터 먹지말고, 이해가 안된다면 하나의 케이스에 대해 손으로 구현하면서 이해해보고 코드 작성으로 넘어가는게 좋을 것 같다.