[프로그래머스][2020카카오공채] 문자열 압축 (level 2) (java)

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

코딩테스트 연습 - 문자열 압축 | 프로그래머스

 

 

 

방법 1 : 길이만 구하기

class Solution {
    public int solution(String s) {
 
        if (s.length() <= 1) {
            return s.length();
        }
        
        int iMin = 1000;
 
        // 단위를 늘려가며 문자열 자르기 반복문
        for (int iUnit = 1; iUnit <= s.length() / 2; iUnit++) {
 
            int iBefore_Count = 1;
            int iSum = 0;
            int iUnitCount = (int) Math.ceil(s.length() / (double) iUnit);
            String strNow = "";
            String strNext = "";
            
            // 배열 현재값과 다음값 비교 반복문
            for (int i = 0; i < iUnitCount - 1; i++) {
                
                // 길이별로 복사해서 문자열 할당
                strNow = s.substring(i * iUnit, (i + 1) * iUnit);
                strNext = ((i + 2) * iUnit <= s.length()) 
                        ? s.substring((i + 1) * iUnit, (i + 2) * iUnit) 
                        : s.substring((i + 1) * iUnit);
                
                // 같을 때
                if (strNow.equals(strNext)) {
                    
                    iBefore_Count++;
                    
                    if (i == iUnitCount - 2)  {
                        iSum += (iBefore_Count+"").length() + iUnit;
                    }
                    continue;
                }
                
                // 다를 때
                if (iBefore_Count == 1) {
                    iSum += iUnit;
                }
                if (iBefore_Count > 1) {
                    iSum += (iBefore_Count+"").length() + iUnit;
                }
                iBefore_Count = 1;
                
                if (i == iUnitCount - 2)  {
                    iSum += strNext.length();
                }
            }
 
            // 최소값
            if (iMin > iSum) {
                iMin = iSum;
            }
        }
        return iMin;
    }
}

 

방법2 : 문자열을 구한 후 길이 구하기

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public int solution(String s) {
        
        if (s.length() <= 1) {
            return s.length();
        }
        
        List<Integer> listLength = new ArrayList<Integer>();
        StringBuilder sb = null;
 
        // 단위를 늘려가며 문자열 자르기 반복문
        for (int iUnit = 1; iUnit <= s.length() / 2; iUnit++) {
 
            String[] arrStr = chop(iUnit, s);
            sb = new StringBuilder();
            int iBefore_Count = 1;
 
            // 배열 이전값과 현재값 비교
            for (int i = 1; i < arrStr.length; i++) {
 
                // 같을 때
                if (arrStr[i - 1].equals(arrStr[i])) {
                    iBefore_Count++;
                    continue;
                }
 
                // 다를 때
                if (iBefore_Count == 1) {
                    sb.append(arrStr[i - 1]);
                }
                if (iBefore_Count > 1) {
                    sb.append(iBefore_Count + arrStr[i - 1]);
                }
 
                iBefore_Count = 1;
            }
 
            // 마지막 문자열 처리
            if (iBefore_Count == 1) {
                sb.append(arrStr[arrStr.length - 1]);
            }
            if (iBefore_Count > 1) {
                sb.append(iBefore_Count + arrStr[arrStr.length - 1]);
            }
            
            // 리스트에 결과 문자열 길이저장
            listLength.add(sb.toString().length());
        }
 
        // 최소값 구하기
        int iMin = 1000;
 
        for (int i = 0; i < listLength.size(); i++) {
            if (iMin > listLength.get(i)) {
                iMin = listLength.get(i);
            }
        }
 
        return iMin;
    }
 
    // 문자열 자르기 -> 배열
    public String[] chop(int iUnit, String s) {
 
        if (iUnit == 1) {
            return s.split("");
        }
 
        int index = 0;
        String[] arrStr = new String[(int) Math.ceil(s.length() / (double) iUnit)];
 
        for (int i = 0; i < s.length(); i++) {
            if (i % iUnit == 0) {
                arrStr[index++] = (i + iUnit <= s.length()) ? s.substring(i, i + iUnit) : s.substring(i);
            }
        }
        return arrStr;
    }
}

 

당연히! 

방법 1이 방법 2보다 2배 빨랐다. 

 

생각해보면 문제에서 원하는 답은 '길이'이므로,

정확한 문자열까지는 구할필요가 없는 것이다.

하지만 처음부터 생각이 그에 닿지는 않아서

방법2로 먼저 통과하고 그제서야 방법1을 떠올렸다. 

 

 잡)

이 문제는 지난 9월 시험삼아 카카오 코딩테스트를 치러봤을때 처음 만났던 문제이다.

그때는 알고리즘 공부를 하기 전이었는데

7문제 5시간의 시험에서 딱 1문제라도 푸는게 목표였다.

 

그때 풀려고 시도했던게 이 문제였는데,

그때는 4시간ㅋㅋ 걸려서 구현 비스므리 한 것을 해내고도

테스트 케이스 3~4개에 걸려서 결국 틀렸다.

나중에야 이게 레벨1짜리 문제였다는 걸 알았는데 ㅋㅋ

 

지금은 더 효율적인 방법을 생각하려고 애쓰고 있으니

아주 만족스럽다 :)