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는 알파벳 소문자로만 이루어져 있습니다.
입출력 예
| 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이 됩니다.
문제 풀이
function solution(s) {
var answer = s.length;
let len = s.length;
let arr = [];
for (let i = 1; i<len/2+1; i++) {
let potion = [];
for (let j = i; j<=len; j+=i) {
if(i === j) {
potion.push(s.slice(0,i))
}
else {
potion.push(s.slice(j-i,j))
}
if(len-i < j && s.slice(j) !== "") {
potion.push(s.slice(j))
break;
}
}
arr.push(potion)
}
arr.forEach(el => {
let total = "";
let n = 1;
let str = el[0];
for (let i = 1; i<el.length+1; i++) {
if(str === el[i]) {
n++;
}
else {
if(n === 1) {
total += str
}
else {
total += n + str
n = 1
}
str = el[i]
}
}
if(total.length < answer) answer = total.length;
})
return answer;
}소가 뒷걸음치다 쥐를 잡은 격이 이런거라고 봐도 될까...싶다.
그냥 이건가 싶어서 테스트를 했는데 바로 맞아서 조금 당황했다.
문제를 푸는 방법은
-
문자열 나누기
-
문자열 합치기
두개로 나눠서 생각했다.
var answer = s.length;
let len = s.length;
let arr = [];
for (let i = 1; i<len/2+1; i++) {
let potion = [];
for (let j = i; j<=len; j+=i) {
if(i === j) {
potion.push(s.slice(0,i))
}
else {
potion.push(s.slice(j-i,j))
}
if(len-i < j && s.slice(j) !== "") {
potion.push(s.slice(j))
break;
}
}
arr.push(potion)
}먼저 한개도 문자를 압축시키지 못할 경우의 답은 s.length 였기 때문에 answer = s.length 를 지정했다.
그리고 문자열을 나누기 위해 필요한 s의 길이를 변수 len으로 놓고
이중반복문을 돌렸다.
첫번째 반복문은 몇개로 나눌것인가에 대한 숫자이다. 1부터 시작해서 len/2+1 보다 작게 진행했다. 그 이유는 절반+1 이상은 결국 합쳐지지 않기때문이다.
그리고 다음 반복문은 문자열을 나누는 반복문이다. i와j가 같을 때 즉 첫번째의 경우 s.slice(0,i)를 potion 배열에 넣어줬다.(해시라고 해도 됐는데 그냥 갑자기 요리할 때 재료 나누는걸 포션나누기라고 한다고 해서 생각나서 변수이름으로 넣어줬다... ㅋㅋ)
그리고 그 외의 경우는 s.slice(j-i,j) 를 푸시해줬다. 이렇게 되면 마지막 문자열이 들어가지 못했고 이것을 해결하기 위해
len-i 가 j보다 작을 때 예를 들어
"aabbaccc" 이 경우에 i가 3라면 "aab", "bac", "cc" 이렇게 3조각이 나는데
s.slice(0,3)는 "aab"
(3,6)는 "bac"
(6,9)은 "cc"
가 된다. 하지만 j의 길이가 8까지이기 때문에 9까지 가지못해서 "cc"가 들어가지 못했고
len-i < j
8-3<6 일때 s.slice(j)가 빈 문자열이 아니라면 나머지를 포션에 넣어줬다.
만약 나누어 떨어지게 된다면 빈 문자열이 들어가기 때문에 빈 문자열은 제외했다.
이렇게 문자열을 나눠놓으면 이런 형식으로 바뀐다.
예시 중 하나이며 문자열이 나눠졌기 때문에 합치기를 실행했다.
arr.forEach(el => {
let total = "";
let n = 1;
let str = el[0];
for (let i = 1; i<el.length+1; i++) {
if(str === el[i]) {
n++;
}
else {
if(n === 1) {
total += str
}
else {
total += n + str
n = 1
}
str = el[i]
}
}
if(total.length < answer) answer = total.length;
})위의 각 배열마다 문자열을 합치는 방법이다.
초기 문자열 str 에 배열의 0번째 인덱스를 넣어주고
반복문을 돌려서 str이 el[i] 와 같다면 n에 1을 더해주고 그렇지 않을 경우
n이 1이라면 문자열을 total에 더해줬고
n이 1이 아니라면 total에 n+str을 해주고 n을 1로 바꿔줬다.
그리고 n의 숫자와 상관없이 str을 새로운 el[i]로 바꿔줬다.
처음에 이렇게 진행하니까 마지막 문자열이 total에 안들어가는 문제가 발생했다.
그래서 이것을 해결해주기위해 최대값에 +1(el.length+1)을 해줬고 그렇게 되니 el[i]가 undefined가 되면서 자연스럽게 마지막 문자열까지 들어가게 됐고
total의 길이와 answer의 길이(시작당시 s.length)를 비교해서 더 작은 것을 answer에 넣어줬다.
