프로그래머스 Lv.2 문자열 압축 - JAVA

문제

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.

간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면 "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상으 ㅣ단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

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

 

 

풀이

- solution 함수에서 문자열 길이가 1일때 부터 str.length()까지 전부 압축을 해봐야 한다. 1개로 했을 경우, 2개로 했을 경우..... str.length()까지

이를 함수로 만들면 compress함수를 만들 수 있는데

public int compress(String str, int length){	//주어진 문자열, 점차 변하는 길이
	StringBuilder sb = new StringBuilder();
    
    int count=0;	//같다면 숫자로 체크한다. -> aa일 경우 2로 표시한다.
    String last=""; //비교할 값을 넣는다.
    
    for(String temp : split(str,length)){
    	if(temp.equals(last)){
        	count++; //전에 문자와 뒤에 문자가 같을 경우 count를 증가시킨다.
        }else{	//다를 경우 이제 aa -> 2a로 바꿔야한다.
        	if(count > 1) sb.append(count);	//숫자를 넣어주고
            sb.append(last);	//지금까지 비교했던 값을 넣어준다.	
            last = temp;	//이제 다음 값으로 넣어준다.
            count = 1; //값이 변경되었으니 카운트도 초기화해준다 여기서 0이 아닌 이유는 last값을 한 번 체크했기떄문
            
        }
    }
    if(count >1) sb.append(count);
    sb.append(last);	//마지막 값도 넣어줘야함
    
    return sb.length();	//문자열 길이리턴

}

 

여기서 split 함수는 주어진 문자열과 길이를 바탕으로 문자열을 substring()으로 주어진 length만큼 쪼갠다.

public List<String> split(String str, int length){
		List<String> list = new ArrayList<>();
        
        
        for(int start =0;start < str.length();start += length){
        
        	int end = start + length; //길이가 1이면 substring(0,1)
            if(end > str.length()) end = str.length(); //문자열길이를 넘어가는 걸 막음
            list.add(str.substring(start,end));
        }
        return list;
	
}

 

solution 함수는 길이가 1부터 문자열까지 조회하여 최솟값을 찾는다.

 

아래 정답

import java.util.*;

class Solution {
    public List<String> split(String str,int length){
        List<String> list = new ArrayList<>();
        
        for(int start = 0 ;start < str.length();start += length){
            int end = start + length;
            if(end > str.length()) end = str.length();
            
            list.add(str.substring(start, end));
        }
        return list;
    }
    
    public int compress(String str,int length){
        
        StringBuilder sb = new StringBuilder();
        
        String last = "";
        int count = 0;
        for(String token : split(str,length)){
            if(token.equals(last)){
                count++;
            }else{
                if(count > 1 ) sb.append(count);
                sb.append(last);
                last = token;
                count = 1;
            }
        }
        if(count > 1) sb.append(count);
        sb.append(last);
        
        return sb.length();
    }
    
    
    
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        for(int length = 1; length <= s.length() ; length++){
                int compressed = compress(s, length);
                if(compressed < answer){
                    answer = compressed;
                }
        }
        
        
        return answer;
    }
}