카카오 프로그래머스 / 문자열압축/ JAVA

2019년도 블라인드테스트에 나왔던 1번 문자열 압축 문제 JAVA풀이

문제 : https://programmers.co.kr/learn/courses/30/lessons/60057?language=java

class Solution {
    public int solution(String s) {
        String exStr = s;
        String bufStr = "";
        String resultStr = "";
        int bufCount = 1;
        int resultLen = exStr.length();
        int resultCount = resultLen;

        for(int i = 1 ; i <= exStr.length()/2; i++) {
            for(int j = 1 ; j <= exStr.length()/i; j++) {
                if(bufStr.equals(exStr.substring((j-1)*i , j*i))) {
                    bufCount++;
                }else {
                    if(bufCount != 1) {
                        resultStr += Integer.toString(bufCount);
                        bufCount = 1;
                    }
                    resultStr += exStr.substring((j-1)*i , j*i);
                }
                bufStr = exStr.substring((j-1)*i , j*i);
            }
            if(bufCount != 1) {
                resultStr += Integer.toString(bufCount);
                bufCount = 1;
            }
            if(resultLen % i != 0)
                resultStr += exStr.substring( resultLen - resultLen % i,resultLen);
            if(resultStr.length() < resultCount) {
                resultCount = resultStr.length();
            }
            resultStr = "";
        }
        System.out.println(resultCount);
    return resultCount;
    }
}

주석 단 것은 아래

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String exStr = sc.next();
        String bufStr = ""; //중복 검사를 위한 버퍼
        String resultStr = ""; //중복검사를 거친 결과값 문자열을 저장할 공간
        int bufCount = 1; //중복횟수

        //입력받은 문자열의 길이
        int resultLen = exStr.length();
        //반환할 최종 길이
        int resultCount = resultLen;

        //exStr/2의 몫 갯수만큼 쪼개서 사용합니다.
        for(int i = 1 ; i <= resultLen/2; i++) {
            //i개씩 j개덩어리로 잘라냅니다.
            for(int j = 1 ; j <= exStr.length()/i; j++) {
                //디버그용 계산 결과
                System.out.println("현재 추출한 값 : " + exStr.substring((j-1)*i , j*i)  + "   bufString에 있는 값 :"+bufStr);
                //이전에 계산했던 값과 일치하는지 확인합니다.
                if(bufStr.equals(exStr.substring((j-1)*i , j*i))) {
                    bufCount++;
                }else {
                    if(bufCount != 1) {
                        resultStr += Integer.toString(bufCount);
                        bufCount = 1;
                    }
                    resultStr += exStr.substring((j-1)*i , j*i);
                }
                bufStr = exStr.substring((j-1)*i , j*i);
            }
            //나머지 처리
            if(bufCount != 1) {
                resultStr += Integer.toString(bufCount);
                bufCount = 1;
            }
            if(resultLen % i != 0)
                resultStr += exStr.substring( resultLen - resultLen % i,resultLen);
            System.out.println("모든  결과 : "+resultStr);

            //만약 1로 쪼갰을 때의 길이보다 작다면
            if(resultStr.length() < resultCount) {
                resultCount = resultStr.length();
//                System.out.println("최선의 결과 : "+resultStr);
            }
            resultStr = "";
        }
        System.out.println(resultCount);
    }

}

이 문제는 앞에서부터 하나씩, 두 개씩, 세 개씩 잘라냅니다.
"aabbaccc"( length = 8 )을 한 개씩 두 개씩... 잘라내보면
a
a
b
b
a
c
c
c

aa
bb
ac
cc

aab
bac
cc

aabb
accc

aabba
ccc

이런식으로 된다는 것을 보실 수 있는데 4개 이상부터는 중복될 수 없게 잘립니다. 때문에 4개까지만 자르면 되겠네요.
이는 length = 8이기 때문입니다.
"aabbaccca" length = 9일 때도 마찬가지로
aabb
accc
a

aabba
ccca

4개일 때는 중복되는 것을 찾아 압축할 여지가 있지만 5개부터는 압축시킬 수 없습니다.
그러니 문자열은 length/2개까지만 잘라내면 됩니다.

그럼 2개씩 잘라내볼게요

String exStr = "aabbaccc"; //길이: 8 요소인덱스 :0,1,2,3,4,5,6,7

        System.out.println(exStr.substring(0, 3)); //0,1,2 요소를 잘라 반환합니다.
        System.out.println(exStr); //잘라서 반환할 뿐, 실제 메모리상 문자열이 제거되지 않습니다.

        for(int i = 1 ; i <= exStr.length()/2; i++) {
            System.out.println(exStr.substring((i-1)*2 , i*2));
        }

이렇게 두 개씩 잘 잘린 것을 확인하실 수 있습니다.
2개씩 자를 때 인덱스가 "aabbaccc"; //길이: 8 //인덱스 0,1,2,3,4,5,6,7
0, 1
2, 3
4, 5
6, 7
이렇게 잘리는데
이를 for(int i = 1 ; i <= exStr.length()/2; i++)
{ System.out.println(exStr.substring((i-1)*2 , i*2)); }로 표현할 수 있습니다.

그렇다면 3개 일땐 어떨까요?
for(int i = 1 ; i <= exStr.length()/2; i++)
{ System.out.println(exStr.substring((i-1)*3 , i*3)); }
이면 됩니다.

이걸 이해하고 위의 코드를 보시면 편하실거에요~

문자열을 잘라낸다음 버퍼에 담아놓고 다음에 잘린 문자열이 지금과 같은지 확인합니다.

같으면 Count를 올리고

다르면 결과문자열공간에 추가합니다. 만약 Count가 1이 아니면 숫자만 추가해줍니다. 그 이유는 

aabbaaaaaabb가 있다고 하면

aa bb aa aa aa bb로 쪼개졌을 때

resultString = ""

int Count = 1;

aa    buf = ""   -> 버퍼와 값이 다르므로 resultString = "aa" 추가해줌

bb   buf = "aa" -> 버퍼와 값이 다르므로 resultString = "aabb" 

aa   buf = "bb" -> 버퍼와 값이 다르므로 resultString = "aabbaa" 

aa   buf = "aa" -> 버퍼와 값이 같으므로  Count = 2;

aa   buf = "aa"  -> 버퍼와 값이 같으므로  Count = 3;

bb   buf = "aa"  -> 버퍼와 값이 다르므로 resultString = "aabbaa3"

이렇게 Count값이 1이 아닌 경우에는 이미 단위 문자열이 들어간 상태이므로 숫자만 따로 추가해줍니다.

이 문제는 나머지처리가 좀 귀찮은데,

aabbaaaaaa인경우

aa bb aa aa aa로 쪼개졌을 때

resultString = ""

int Count = 1;

aa    buf = ""   -> 버퍼와 값이 다르므로 resultString = "aa" 추가해줌

bb   buf = "aa" -> 버퍼와 값이 다르므로 resultString = "aabb" 

aa   buf = "bb" -> 버퍼와 값이 다르므로 resultString = "aabbaa" 

aa   buf = "aa" -> 버퍼와 값이 같으므로  Count = 2;

aa   buf = "aa"  -> 버퍼와 값이 같으므로  Count = 3;

Count만 올라가다 같은 경우에서 끝나버렸으므로 남은 Count를 따로 결과값에 추가해주어야하고,

(->원래 문자열압축 모양과 숫자의 위치가 다르긴하지만 길이만 반환하면 되니까 이렇게 만들었습니다.)

aabbaaaaaab인경우

aa bb aa aa aa b로 쪼개졌을 때

resultString = ""

int Count = 1;

aa    buf = ""   -> 버퍼와 값이 다르므로 resultString = "aa" 추가해줌

bb   buf = "aa" -> 버퍼와 값이 다르므로 resultString = "aabb" 

aa   buf = "bb" -> 버퍼와 값이 다르므로 resultString = "aabbaa" 

aa   buf = "aa" -> 버퍼와 값이 같으므로  Count = 2;

aa   buf = "aa"  -> 버퍼와 값이 같으므로  Count = 3;

b   <- 이렇게 홀로 남는 친구들은 결과값 뒤에 추가해주어야합니다.

 

그래서 최선의 결과 길이만 반환하면 끝~!