문제 설명
"aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
- 입출력 예
#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 arr: [String] = []
var result: String = ""
var resultCount: [Int] = []
var count: Int = 1
var temp: String = ""
if s.count <= 2{
return s.count
}
for i in 1...s.count/2 {
var s = s
var str = ""
//단위에 따라 문자열 자르고 배열에 추가
for j in s{
str.append(j)
s.removeFirst()
if s.isEmpty {
arr.append(str)
continue
}
if str.count == i {
arr.append(str)
str = ""
}
}
//문자열을 압축
for element in arr {
if temp == "" {
temp = element
continue
}
if temp == element {
count += 1
continue
} else {
if count == 1 {
result += temp
temp = element
} else {
result += "\(count)\(temp)"
temp = element
count = 1
}
}
}
if count == 1 && !temp.isEmpty {
result += temp
} else if count >= 2 {
result += "\(count)\(temp)"
}
count = 1
temp = ""
resultCount.append(result.count)
result = ""
arr = []
}
return resultCount.sorted { $0 < $1}[0]
}이번 문제는 너무 오래걸렸다. 1단계 문제들이 생각보다 금방 풀려서 2단계 문제를 풀어봤는데 아직까지 실력이 너무너무 모자라다는 것을 느꼈다. 근데 막상 다른 분들 코드를 참고하며 풀고 나니 왜 이 생각을 못했을까라는 생각도 들고, 생각한대로 코드가 구현이 안돼서 힘든 점도 있었다.
먼저 문자열을 1부터 s.count/2의 크기로 나눠서 배열에 넣어주도록 하였다. 다음 요소와 중복되는지 확인하려면 남은 부분이 크기와 같거나 커야하므로 문자열의 크기가 s.count/2를 넘어갈 수 없다.
다음으로 배열에 있는 요소들을 하나씩 확인하며 temp가 비어있을 경우엔 해당 element를 넣어주도록 하였다. 만약 temp에 들어있는 요소와 해당 element가 같을 경우엔 같은 문자열의 수가 하나 늘어나는 것이므로 count에 1을 더해주었다.
이때 count의 초기값은 1로 해주어 1일 경우엔 temp에 들어있는 값만, 아닐 경우엔 문자열 앞에 count값도 붙여주어 result라는 변수에 담게 하였다.
이때 i의 크기보다 작은 문자열이 남아있는 경우가 있다. 이럴 경우엔 count가 1이며 temp가 비어있지 않은 경우에 그 값을 추가해주도록 하였다. 만약 남은 문자열들이 같은 문자열들이라면 위의 코드로는 count만 올라간채 result에 포함이 되지 않았을 것이므로 이 경우까지 생각해주어 추가해준다.
#예시#
다시 한 번 압축 구조를 설명하자면 예를 들어 aabbaccc라는 문자열이 있다고 해보자. 문자열의 크기가 1인 문자열로 나눈 경우만 설명해보겠다.
먼저 첫번째 for문의 i가 1인 상태이다. str이라는 String에 문자를 추가해가며 str의 크기가 i와 같아졌을때 str값을 배열에 넣어주고 str을 다시 빈 상태로 초기화시켜준다. 이 단계를 거치면 배열 안엔 ["a","a","b","b","a","c","c","c"] 의 형태로 들어있을 것이다.
다음으로 문자열을 압축할 차례이다. 위 배열의 요소들로 차례대로 for문을 돌린다. 일단 temp라는 문자열이 비어있을 경우엔 해당 element를 넣어주도록 한다. continue가 있으므로 다음 요소인 두번째 "a"가 element가 된다. 이때 temp와 element를 비교하며 같을 경우엔 count에 1을 더해주고, 같지 않을 경우엔 두 가지 경우로 나눠서 확인한다.
(temp와 element가 같지 않은 상태)먼저 count가 1인 경우엔 temp에 들어있는 요소 다음에 바로 temp와 다른 element가 들어오는 경우이다. 이때는 문자열이 축약되지 않는 경우라서 count없이 result에 바로 temp를 추가해준다. 그 뒤 temp를 element값으로 넣어준 뒤 다음 요소와 다시 비교를 시작한다. 만약 count가 1이 아니라면 축약이 가능한 상태이므로 축약된 횟수인 count와 temp를 합쳐 result에 추가한 뒤 count값을 다시 1로 만들어준다.
다음으로 뒤에 남아있는 것들이 있다면 위에 말한 방식으로 result에 추가해준다. 이렇게 문자열의 크기 별로 result에 넣고 각각의 크기를 resultCount에 Int형태로 넣어 sorting한 뒤 가장 작은 값을 출력해주도록 하였다.
개인적으로 어려웠던만큼 자세하게 설명하다보니 길어졌다. 근데 설명하며 구조를 확인하면 참 간단한 문제같은데 아직까지 구현 실력이 많이 모자라는 것 같다.
