문자열 압축

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

코딩테스트 연습 - 문자열 압축

 

문제해결방식

 /*
        *
        *   1. 1개나누기 2개나누기 3개나누기로 가므로 최대 나눌수있는 개수를 구해 최대개수까지 실행한다.
        *
        *   2. 위에서 정해준 나눌 개수대로 구하며 문자열을 압축한다.
        *          문자를 가져와 같지않을때까지 값을 구한다.
        *
        *
        *   3. 압축한 문자열과 지금 최소 문자열길이를 비교해 더작은것을 입력해놓는다
        *
        * */

의사코드를 작성하였지만 index에 대한 부분을 제대로 작성하지 못하였고 머리로만 그리려니 힘들었다..

index에 관한부분을 의사코드로 어떻게 작성하면 좋을지 생각을 해봐야겠다..

 

또한 문제 해결에대한 여러가지 접근 방식이있는데

1.prev값과 now값을 가져와 비교하고 같지않으면 prev값을 넣는 방식

2.now와 next를 구해 같지않으면 now를 넣는 방식이 있는데 

여러가지 접근방식을 생각해보고 어떤것이 더 코드로 보았을때 쉬울 것같은지와 어떤것이 더효율적인 알고리즘인지를 생각을 해보는 시간이 있어야겠다..

 

 

개선한 코드

for(int i=cut;i<=s.length();i+=cut)

s.length전까지만 맨날 구해왔는데 s.length까지 구해야 하는것을 처음 느껴봤다

index에 대한 어려움이 많이 있는데 outBoundException을 어떻게 잘처리할지를 언제한번 잘정리를 해보고 index에 관해 정리를 해보는 시간이 있어야겠다..

 

ex) str이 aa고

s.length전까지 구하게되면 해당코드에서는 prev값을 두어 1부터 시작하는데 i++가된다면 a 만 들어가게 되고 바로끝난다

s.length까지 구하게 되면 길이가 2일때 1부터 시작하더라도 2일때 들어가 prev와 now(허수)를 비교해 같지않으니 들어가게 만들어준다  전까지와 까지가 이렇게 한끗차이지만 많은 변화를 일으킬 수 있다.. 

package programeers.level2;

public class 문자열압축 {
    public static void main(String[] args) {

        System.out.println(solution("aaaabbbb"));
    }
    /*
    *
    *  배운점 substring의 beginindex는 length가 넘는값이 와도되고 endIndex는 length까지만 와야함
    *
    * */
    public static int solution(String s) {
         int answer=s.length();
         for(int cut=1;cut<=s.length()/2;cut++){
             String res="";
             String prev=s.substring(0,cut);
             String str=prev;
             int cnt=1;
             for(int i=cut;i<=s.length();i+=cut){
                 //<=로하는이유  aaaa로 4a를 하고 bbbb로 cnt를 4로만들지만 7이 되버리므로 끝나게됨
                 //<=를 통해 now에 ""를 넣게하여 cnt가 들어간 값은 넣게해줌
                 String now=i+cut>s.length() ?  "" : s.substring(i,i+cut);
                 str+=now;
                 if(prev.equals(now)){
                     cnt++;
                 }else{
                     if(cnt!=1){
                         res+=cnt;
                     }
                     res+=prev;
                     cnt=1;
                     prev=now;
                 }
             }
             //혹시모를 남아있는 값들이 안들어가있을수 있기때문에 넣어줌
             //ex) aaaabbbb를 3으로한다면 aaaaabb까지만들어가게됨 왜냐하면 length가 8인데 3+3+3이되게되서 9가나오게되므로 못들어가는게있음
             if(str.length()<s.length()){
                 res+=s.substring(str.length(),s.length());
             }
             System.out.println(res);
             answer=Math.min(answer,res.length());
         }
        return answer;
    }
    //https://jithub.tistory.com/3
    public static String padRight(String s, int n) {
        int len= s.length()+n;
        return String.format("%-"+len+"s", s,n);
    }
}

IDE를 쓰지 못한다 하면 시간이 오래걸리긴하지만 한번 변할때마다 sout처럼 값을 적으면서 테스트 하는게 좋을것같다.

이렇게 나올거고 이렇게 나올거고 3~4개정도만 나와도 눈에보이니까 이해하는데 도움이 많이됨 

 

 

첫번째 코드

package programeers.level2;

public class 문자열압축 {
    public static void main(String[] args) {
        System.out.println(solution("aabbc"));
    }
    public static int solution(String s) {
        int answer = 1001; // s의 길이는 1 이상 1,000 이하입니다. 제일작은것을 구해야하니 값을 1001 입력

        int len = s.length()/2; // 1 2 3 4 가 있을때 최대 12 34 이렇게만 나눌 수 있음 그러므로 길이 / 2
        
        for(int k=1;k<=len;k++){
            int cnt=1;
            String res="";
            String original="";
            for(int i=0;i<s.length()-k;){//값을 가져올때 왼쪽값
                int j= i+k;
                String comparison = s.substring(i,j);
                original+=comparison;
                for(int q=j;q<s.length();q+=k){
                    if(q+k>s.length()) break;

                    if(comparison.equals(s.substring(q,q+k))){
                           original+=comparison;
                           cnt++;
                           i=i+k;
                    }else{
                         break;
                    }
                }
            if(cnt!=1){
                res+=cnt;
            }
                res+=comparison;
                cnt=1;
                i=i+k;
            }
            if(original.length() < s.length()){
                res+=s.substring(original.length(),s.length());
            }
            if(res.length()<answer){
                answer=res.length();
            }
        }
        return answer;
    }

}

내가 풀고도 왜 성공했는지 잘모르겠는 코드.. 이따 다시한번 보면서 정리해야겠다..

 

 

내가 배워야할 코드 

한개씩만 자르는문제인데 i+=count로 i의 값을 잘 이동시켜주었다

또한 한개씩만 자를때 마지막 값이 비교안될 수 있는데 그때 문자에 " "  공백한게 추가해주면 마지막 값도 비교하게됨

import java.util.*;

public class Solution { 
    public String compressString(String str) {
        if(str.isEmpty()) return str;  // 빈 문자열이면 그대로 반환
        char[] charArray = str.toCharArray();  // 입력 문자열 char[]으로 변환
        StringBuilder ret = new StringBuilder();  // 반환할 문자열을 저장

        for(int i = 0; i < charArray.length;) {  // charArray의 length 만큼 반복. 증감문 제외 이유는 아래 로직에서 i를 더하기 때문
            int count = 1;  // charArray[i] 값을 카운트하기 때문에 기본값 1
            for(int j = i + 1; j < charArray.length; j++) {  // i + 1 값으로 초기화하여 charArray의 length 만큼 반복
                if(charArray[i] == charArray[j]) count += 1;  // charArray[i]와 charArray[j]가 같으면 count 1 증가
                else break;  // 다르면 바로 탈출
            }
            if(count > 2) {  // count가 3 이상인 경우
                ret.append(count).append(charArray[i]);  // 반환할 문자열에 "count + 문자" 추가 (예 : 3a)
                i += count;  // count 만큼 동일 문자이기 때문에 index에 더하여 통과
            } else {
                while(count > 0) {  // count가 0보다 크면 반복. 최소 1회, 최대 2회 반복
                    ret.append(charArray[i]);  // 반환할 문자열에 "문자" 추가 (예 : a)
                    i += 1;  // index 1 증가
                    count -= 1;  // count 1 감소
                }
            } 
        }
        return ret.toString();
    } 
}