카카오 코딩테스트 기출, swift 문자열압축 문제풀이

 

 

안녕하세요? iOS Developer, 멍구입니다. 🤗

오늘은 프로그래머스의 카카오 기출 알고리즘 문제 중 하나인 문자열 압축 문제를 swift로 풀어보도록 하겠습니다. 먼저, 문자열 압축 문제 설명을 보도록 하겠습니다.

 

 

---

카카오 코딩테스트 기출, 문자열 압축 문제 설명

문자열 s가 입력값으로 주어질 때, 1개 이상 단위로 문자열을 잘라 압축 표현이 가능할 때, 가장 짧은 경우의 길이를 구하는 문제입니다.

여기에서 주의할 점은, n개 길이단위로 잘라서 압축을 시도할거라면, 반드리 n개 단위로만 잘라야 한다는 것입니다. 예를들면, 처음에 2개씩 자르다가 1, 3개씩 자르는게 불가능 합니다. 또한, 처음부터 일정하게 n개씩 잘라서 봐야한다는 것입니다. 

예를들면, abcde를 2개씩 잘라서 압축하려한다면, ab, cd, e 의 형식으로 동등한 2의 길이로 잘라서 봐야 합니다. (물론 맨 끝에 남은 꼬리 문자열은 n 미만의 길이일 수도 있겠죠)

문자열압축 문제의 제한사항도 보도록 하겠습니다.

 

 

s의 길이는 1이상 1,000이하고, 알파벳 소문자로만 이루어져 있어서, 대소문자 구분은 필요가 없겠습니다. 

첫번째 입력 예시인 "aabbaccc"는 1개씩 잘라서 압축했을 때 가장 짧은 문자열입니다. "2a2ba3c" 로 7의 길이를 갖습니다.

한번 반복되는 경우에는 1을 붙이지 않습니다.

 

또 하나 주의해야할 점은 중복되는 횟수가 10, 100이 될 수도 있습니다. 그러므로, 10a100b100c 와 같은 문자열압축 결과가 생길 수도 있습니다.

그러므로, 중복된 문자열의 압축을 했을때, 10이상, 100이상의 반복이 되었다면, 반복횟수의 문자열 길이를 1이상인 2, 3으로 계산해야할 수도 있다는 것을 주의해야 합니다. (저도 이걸 생각못해서 버벅였네요 ㅜ.ㅜ)

이제 해당 카카오 코딩테스트 문제, 문자열압축을 코드로 구현해보겠습니다.

 

 

---

카카오 코딩테스트 기출, 문자열압축 swift 코드 작성

1행) Foundation은 이번 문제의 경우 import할 필요는 없었지만 기본으로 작성되어있는 코드로 그냥 두었습니다.

3 ~ 11행) dupLen 메서드는 중복문자열 압축 시 추가로 앞에 생기는 중복횟수 값의 문자열 길이를 구하는 문제입니다. 0...9는 1자리, 10 ... 99는 2자리, 100 ...999는 3자리의 길이를 갖겠죠. 해당 부분을 체크하는 메서드를 따로 분리해봤습니다. 

 

 

13 ~ 14행) 실제 메인 메서드입니다. 먼저 입력으로 받는 문자열을 배열화했습니다. 

15 ~ 16행) 배열 최대길이, 정답으로 반환할 변수 Ans를 초기화 했습니다.

18행) mxLen 이 2 이하일 경우에는 해당 길이 그대로 답으로 반환하면 됩니다. 중복 압축이 발생하던 안하던간에 입력 문자열길이가 1이면 1을, 2이면 2를 답으로 반환하면 됩니다.

 

 

19행) 바깥 for문은 잘라낼 문자열 길이단위를 나타냅니다. 1개씩 잘랐을때 압축길이 -> 2개씩 잘랐을때 압축길이 .... mxLen/2개씩 잘랐을때 압축길이를 체크하며 최소길이를 구하는 방식입니다. 

mxLen/2개씩 자를때까지만 순회하는 이유는 그 이후의 길이씩 자를 경우 중복되는 문자열이 나오지 않기 때문입니다. "aaa"의 문자열을 2개씩 잘랐을때 "aa", "a"가 되는데 절대 중복 문자열이 나올 수 없겠죠?

 

20 ~ 24행) STK는 n개 단위로 잘라낸 문자열을 이전 n개 길이의 문자열과 비교할 때 활용합니다. 또한 압축길이 계산할때도 사용하게 됩니다.
- cnt는 현재 문자열의 길이 체크에 사용합니다.
- dup는 중복횟수를 카운팅합니다.
- addLen은 중복횟수인 dup값이 매겨질때 해당 중복표시 문자열의 길이를 계산하는데 사용합니다. 예를들면, "20d123ad" 문자열의 경우, addLen은 5가 됩니다. 
- str은 n개 단위로 잘라낸 문자열을 만들어 체크하는데 사용합니다. 

 

 

 

25행) 내부 for문입니다. 문자열배열을 순회하면서 len 길이 단위로 잘라내어 이전 len 길이 문자열과 비교하며 중복여부를 체크하고, 압축길이를 계산합니다. 

26 ~ 27행) len 길이의 문자열 str을 만들며 cnt로 현재 문자열 길이도 체크합니다. 

28 ~ 30행) 만약 cnt == len이 되었다면 현재 만들어진 문자열 str을 이전의 문자열과 비교합니다. 만약 중복이 된다면 dup += 1로 중복횟수를 카운팅합니다. 

31 ~37행) 만약 이전의 문자열과 중복되지 않는다면, 해당 문자열은 STK에 누적시킵니다. 또한 이전까지 중복카운팅값이 1 이상일 경우 2이상의 중복이 존재했다는 것이므로, addLen += dupLen(of: dup)로 중복횟수에 따른 문자열 길이를 추가시킨 후, dup = 1로 중복횟수를 초기화 시켜줍니다. 

38 ~ 39행) 이후의 문자열을 다시 생성 후 비교하는 것을 반복하기 위해 cnt, str를 초기화 시켜줍니다. 

42 ~ 43행) 이렇게 현재 len을 기준으로 압축길이 결과를 연산합니다. STK.count는 누적된 순수 영문 문자열이 담겨있는데, 여기에 누적된 STK.count에 * len을 곱해줘야 합니다. (실제 길이는 n길이로 잘라낸 문자열들이 모여 있고, 문자 하나 당 1의 길이를 갖기 때문입니다.)

또한 앞서 구했던 addLen의 길이를 더해주고 추가로 dup값이 2이상일 경우, dupLen(of: dup) 메서드 결과를 한번더 누적시켜줍니다. for문이 순회가 끝났을때 미쳐 맨 끝의 문자열 압축결과가 누적되지 않을 수 있기 때문입니다. 

그 후에 Ans값과 현재 구한 문자열 압축길이를 비교해서 최솟값을 저장합니다. 이를 1 ~ mxLen/2 길이단위로 잘라보면서 문자열압축길이를 비교하면 끝입니다. 

 

 

이렇게 연산이 된 Ans 변수를 반환하고 끝이납니다. 

 

 

 

오늘은 카카오 코딩테스트 기출문제 중 하나인 문자열압축 문제를 풀어봤습니다.

그렇게 복잡한 문제가 아닌것 같다가도, 10 ~ 100 ~ 의 중복횟수가 있을 경우 등을 감안해야하는 부분 등이 있어서 꼼꼼하게 풀지 않으면 모든 케스트케이스를 통과할 수 없는 문제이기도 했습니다. 이런 문제는 당황하지말고, 문제를 찬찬히 읽어가며 의도에 맞게 풀어가야 할 것 같습니다. 😁