[프로그래머스] Lv.2 문자열 압축 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

 

문제 설명

문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현해 더 짧은 문자열로 줄여서 표현하려고 합니다.

 

예시

예시 문자열	압축 단위	압축된 문자열
"aabbaccc"	1	"2a2ba3c"

예시 문자열	압축 단위	압축된 문자열
"ababcdcdababcdcd"	2	"2ab2cd2ab2cd"
	8	"2ababcdcd"

 → 8개 단위로 압축한 문자열의 길이가 더 짧다.

예시 문자열	압축 단위	압축된 문자열
"abcabcdede"	2	"abcabc2de"
	3	"2abcdede"

→ 3개 단위로 압축한 문자열의 길이가 더 짧다.
이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

 

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해 주세요.

* 주의 사항 : 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다! *

---

💡 아이디어

빨간색으로 표시한 주의사항을 잘 고려하여 문자열 압축 하는 것에 주의합니다.!

 

예를 들어,

주어진 문자열 "xababcdcdababcdcd" / 자르는 단위: 2

xa ba bc dc da ba bc dc d

앞에서부터 잘라야 하기 때문에 위와 같이 나눠지므로 압축할 수 없습니다.

 

주어진 문자열 "abcabcabcz" / 자르는 단위: 3

abc abc abc z → 3abcz

3개의 단위로 자르고 남은 문자열(z)은 그냥 뒤에 붙여주면 됩니다.

 

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해 주세요.

* 주의 사항 : 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다! *

---

💡 아이디어

빨간색으로 표시한 주의사항을 잘 고려하여 문자열 압축 하는 것에 주의합니다.!

 

예를 들어,

주어진 문자열 "xababcdcdababcdcd" / 자르는 단위: 2

xa ba bc dc da ba bc dc d

앞에서부터 잘라야 하기 때문에 위와 같이 나눠지므로 압축할 수 없습니다.

 

주어진 문자열 "abcabcabcz" / 자르는 단위: 3

abc abc abc z → 3abcz

3개의 단위로 자르고 남은 문자열(z)은 그냥 뒤에 붙여주면 됩니다.

---

📖 풀이 과정

 1. 문자열 압축 단위를 1부터  s길이/2까지 반복합니다.

(중복된 문자열이 2개 이상일 때부터 압축할 수 있기 때문에 압축단위는 s/2까지만 계산합니다.)

 

2. 압축 단위로 자른 이전 문자열이 현재 문자열과 같다면, 중복 문자열 개수+1해 줍니다.

ab -> dupCnt=1
ab ab -> dupCnt=2
ab ab ab -> dupCnt=3

 

3. 이전 문자열과 다르다면, 기존에 저장했던 중복문자열을 새로운 문자열(comp)에 저장해 줍니다.

여기서 만약 이전 문자열이 중복되었던 문자열이라면 "중복된 개수+중복문자열"을 comp에 더해줍니다.

ab -> dupCnt=1
ab ab -> dupCnt=2
ab ab cd -> comp+="2ab"
                   dupCnt=1(초기화)

 

4. 문자열 압축 단위만큼 검사를 다 한 후에 마지막 문자열은 comp에 추가되지 않고 나오기 때문에,

마지막 저장된 문자열을 comp에 추가해 줍니다.

 

5. 그리고 문자열 압축 단위로 나눠 떨어지지 않아, 뒤에 남는 문자열은 그냥 붙여줍니다.

 

6. 2~5번까지의 과정을 거쳐 나온 comp(압축문자열)의 길이가 answer보다 작으면 answer에 저장합니다.

---

전체 코드

class Solution {
    public int solution(String s) {
        int answer = s.length();
        
        for(int i=1;i<=s.length()/2;i++){//문자열 압축 단위
            
            String dup="";//중복 문자열
            int dupCnt=1;//중복 count
            String comp="";//압축 문자열 : s를 i단위로 압축
            
            int j=0;//s문자열에서 j번째부터 j+i번째문자까지 자름.
            for(j=0;j+i<=s.length();j+=i){
                
                if(s.substring(j,j+i).equals(dup)){//기존의 중복문자열과 같으면 
                    dupCnt++;                       //중복 count+1
                    
                }else{//기존의 중복문자열과 다르면
                    if(dupCnt>1) comp+=dupCnt+dup;//중복 개수+중복문자열
                    else comp+=dup;//중복개수가 1개면 압축 x -> 이전 문자열만 입력
                    
                    dupCnt=1;//중복 개수 초기화
                    dup=s.substring(j,j+i);//다움 문자열 중복 검사를 위해 dup에 넣어줌.
                }
            }
            //마지막에 중복 문자열 저장만 되고 나오기 때문에
            //마지막 문자열 comp에 넣어줌.
            if(dupCnt>1) comp+=dupCnt+dup;
            else comp+=dup;
            
            //문자열 s가 압축단위(i)로 나눠떨어지지 않아
            //문자열이 남는 경우
            //ex - abab abab cc (압축단위:4)
            comp+=s.substring(j,s.length());
            
            //기존보다 문자열길이가 작으면 저장.
            if(comp.length()<answer) answer=comp.length();
        }
        
        return answer;
    }
}