문자열 압축

유태형·2022년 3월 21일

코딩테스트 프로그래머스

프로그래머스 - Level 2

목록 보기

34/36

문제

문제 분석

문자열 묶음으로 압축하여 가장잘 압축될 수 있는 문자열의 수를 구해 길이를 구하는 문제입니다.

풀이

압축을 위해 실제로 문자열을 수정하고 했지만 이 문제는 문자열이 아닌문자열의 길이를 제출하는 문제입니다. 형식에 얽매여서 풀이가 많이 힘들었었습니다.

시작위치와 갯수

시작위치와 갯수로 문자열 묶음을 구분합니다. j는 묶음의 시작위치, i는 묶음의 갯수를 세어 문자열 묶음의 갯수당 압축율을 구합니다.

		//i=길이, j=시작위치
        for(int i=1;i<s.length()/2+1;i++){
            String prev = s.substring(0,i); //시작 문자 묶음
            int count = 1; //연속되는 갯수
            String temp = ""; //버퍼
            String last = ""; //마지막은 따로(묶음 갯수와 남은 문자갯수는 다를수 있음)

temp는 현재 압축한 문자열, last는 마지막 나머지를 처리하기 위한 문자열

문자열 묶음 비교

			for(int j=i; j<s.length(); j+= i){
                if(j+i>s.length()){
                    last = s.substring(j);//남은 문자열이 i보다 작은경우
                    continue;
                }
                if(prev.equals(s.substring(j,j+i))) //연속
                    count++; //갯수 증가
                else{
                    temp += prev; //길이만 맞추자! 꼭 압축 형식 맞출 필요 없는 문제!
                    if(count > 1){ //연속
                        temp = count + temp; //숫자 추가
                    }
                    prev = s.substring(j,j+i);
                    count = 1;
                }
            }

j+i > s.length()로 남은 문자열을 비교하고 prev.equals(s.substring(j,j+i))로 문자열이 연속 되는지 셉니다. count는 몇번 연속되었는지 세고 prev는 이전문자열로 연속성을 비교하기 위해 사용 됩니다.

나머지 문자열 처리와 압축 비교

			temp += prev + last; //마지막 나머지
            if(count > 1)
                temp = count + temp;
            
            //최소 길이 비교
            if(answer > temp.length())
                answer = temp.length();

마지막 나머지 부분을 추가하고 최소길이 인지 비교합니다.

코드

class Solution {
public int solution(String s) {
    int answer = s.length(); //1단위 일때 최소
   
    //i=길이, j=시작위치
    for(int i=1;i<s.length()/2+1;i++){
        String prev = s.substring(0,i); //시작 문자 묶음
        int count = 1; //연속되는 갯수
        String temp = ""; //버퍼
        String last = ""; //마지막은 따로(묶음 갯수와 남은 문자갯수는 다를수 있음)
   
        for(int j=i; j<s.length(); j+= i){
            if(j+i>s.length()){
                last = s.substring(j);//남은 문자열이 i보다 작은경우
                continue;
            }
            if(prev.equals(s.substring(j,j+i))) //연속
                count++; //갯수 증가
            else{
                temp += prev; //길이만 맞추자! 꼭 압축 형식 맞출 필요 없는 문제!
                if(count > 1){ //연속
                    temp = count + temp; //숫자 추가
                }
                prev = s.substring(j,j+i);
                count = 1;
            }
        }
        temp += prev + last; //마지막 나머지
        if(count > 1)
            temp = count + temp;
       
        //최소 길이 비교
        if(answer > temp.length())
            answer = temp.length();
    }
   
    return answer;
}

}