문제설명
- 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 표현하는 알고리즘 구현
- 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현하는 방법 찾기
1) ababcdcdababcdcd -> 1개 단위 ababcdcdababcdcd
2) ababcdcdababcdcd -> 2개 단위 2ab2cd2ab2cd
3) ababcdcdababcdcd -> 8개 단위 2ababcdcd(가장 짧은 문자열)
- 압축할 문자열 s를 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 반환
제한사항
- s의 길이는 1이상 1,000이하
- s는 알파벳 소문자로만 구성
풀이
function solution(s) {
const result = [];
const reduceResult = [];
let index;
let reduceString='';
for(let i=1;i<=s.length/2;i++){
index = 0;
while(true){
const word = s.substr(index,i);
result.push(word);
index += i;
if(index > s.length-1){
result.push('/');
break;
}
}
}
let check = 1;
for(let i=0;i<result.length;i++){
if(result[i] === result[i+1])
++check;
else if(result[i] === '/'){
reduceResult.push(reduceString);
reduceString = '';
}
else{
if(check !== 1){
reduceString += `${check}${result[i]}`;
check = 1;
}else{
reduceString += result[i];
}
}
}
let minLength = 1000;
reduceResult.map(result=>{
if(result.length<minLength)
minLength = result.length;
});
if(s.length===1)
return 1;
else
return minLength;
}
체크포인트
- 문자열이 반복되는 경우를 찾아야하므로 문자열 길의 절반 단위까지만 확인
- 문자열 s의 길이가 1인 경우 압축 문자열은 빈배열로 나오므로 마지막에 따로 1 반환하기