알고리즘🅰/프로그래머스

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

개발조각 2022. 5. 2. 18:03
728x90
반응형

이번 문제는 전에 풀다가 포기했었는데

그래도 다시풀어보자해서 풀어보려 하니까 좋은 아이디어가 생각나서 바로 풀었습니다.ㅋㅋㅋ

접근방법

이 문제는 문자열을 1개씩~ ?개씩 압축할 시 가장 짧게 압축된 문자열의 길이를 구하면 됩니다.

그래서 저는 어떻게 구했나면

  • 1 ~? 개씩 압축한 문자열의 길이를 배열에 담아주고
  • 배열에서 값이 가장 작은 값을 추출해주었습니다.

 

1~? 개씩 압축한다고 했는데

여기서? 는 s.length/2으로 지정을 해주었습니다.

 

예시) aabbaabb

  • 2a2b2a2b
  • 2aabb -> s.length/2 압축

최종적으로 압축하면 이럴 경우까지만 있을 거라 생각했고,

s.length/2 이상의 압축은 s.length와 똑같기 때문에 할 이유가 없다고 판단했습니다.

 

 

접근방법을 코드로 작성하면 됩니다.

해결방안

function solution(s) {    
    let compress = [];
    for(let i=1; i<=s.length/2; i++){
        let str ='';
        let count = 1;
        for(let j=0; j<s.length; j+=i){
            if(s.substr(j, i) === s.substr(j+i, i)) count++;
            else{
                str += count === 1 ? s.substr(j, i) : count + s.substr(j, i);
                count = 1;
            }
        }
        compress.push(str.length);
    }
    return s.length > 1 ? Math.min(...compress) : 1;
}

 

for(let i=1; i<=s.length/2; i++)

첫 번째 for문은 1~s.length/2 단위 씩 압축할 단위 값을 지정하는 곳

 

let str ='';
let count = 1;
  • str : s를 i단위로 압축할 때의 값을 넣어주는 문자열
  • count : i단으로 압축할 때 중복된 값이 몇 개인지 표시 (aabbaccc -> 2a2ba3c이면 후자에서 숫자를 의미)

count의 초기값이 1인 이유는 aa을 1 단위로 압축을 할 때 2a가 됨으로 기본값을 1로 넣어주었습니다.

 

for(let j=0; j<s.length; j+=i)

두 번째 for문은 i단위만큼씩 압축을 했을 때 그 단위만큼 s를 이동시키는 곳입니다.

 

if(s.substr(j, i) === s.substr(j+i, i)) count++;
else{
    str += count === 1 ? s.substr(j, i) : count + s.substr(j, i);
    count = 1;
}

substr() 메서드를 써서 문자열 s에서 i 단위만 큼이 무슨 문자열인지 체크하였습니다.

 

만약 현재 위치의 문자열과 다음 위치의 문자열이 같으면 count++을 해주었습니다.

아닐 경우에는 str += count+현재위치 문자열을 해주었는데요.

여기서 count가 1이라는 말은 중복된 값이 없다는 말이 돼서 count가 1이면 s.substr(j, i)을 해주었습니다.

그리고 다음 차례의 중복을 체크하기 위해 count는 다시 1로 변경하였습니다.

 

compress.push(str.length);

위에서 구한 str문자열의 길이를 compress배열에 담아주었습니다.

 

return s.length > 1 ? Math.min(...compress) : 1;

마지막으로 compress에 담은 값 중에서 Math.min을 사용해서 제일 작은 값을 추출했습니다.

여기서 return Math.min(...compress)만쓰면 테스트 5번에서 실패가 뜹니다.

실패가 뜨는 이유는요. 문자열 s가 한 글자일 경우가 있기 때문입니다.

  • s="a", return=1

앞에서 제가 쓴 코드 for(let i=1; i<=s.length/2; i++)를 보시면 s.length/2를 합니다.

그래서 s.length=1인 경우 s.length/2= 1/2 = 0.5 임으로

for(let i=1; i<=s.length/2; i++)이 실행되지 않고 compress=[]이 나옵니다.

 

그래서 이런 경우도 생각을 해야 돼서

저는 s.length > 1인 경우에는 compress에서 제일 작은 값을 추출하고 아닐 경우에는 1을 return 해주었습니다.

여기까지 프로그래머스 문자열 압축 해결방안에 대해 설명해보았습니다.

728x90
반응형