알고리즘(문자열 압축, 큰 수 만들기)

[문자열 압축]

 

* 로직

• 단어의 비교 묶음을 1개부터 (문자열 길이/2)개까지 늘려가면서 압축을 진행한다
• 이전과 같은 문자라면 카운팅을 진행해주고, 그렇지 않다면 이전까지 카운팅된 수에 맞게끔 압축을 진행한다
  • 카운팅된 수가 1개라면 1을 생략한다
  • 2개 이상이라면 숫자를 넣어준다
• (문자열의 길이 / 단어의 비교 묶음)이 홀수라면
  • 문자열의 뒷부분이 고려가 안되기 때문에 따로 남은 부분을 압축된 문자열 뒤에 붙여준다
• 압축된 문자열을 받게되면 해당 문자열의 길이를 세고, 최솟값으로 갱신한다

 

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        if(s.length() == 1) return 1;

        //단어의 묶음을 1개부터 문자의 길이/2까지 나눠서 진행
        for(int i=1; i<=s.length()/2; ++i){
            int idx=0;
            int cnt=1;
            String base = s.substring(idx, idx+=i);
            StringBuilder sb = new StringBuilder("");

            boolean check = false;
            for(int j=1; j<s.length()/i; ++j) {
                check = true;
                String word = s.substring(idx, idx+=i);
                if(base.equals(word)){
                    cnt++;
                }

                else {
                    doCompression(base, cnt, sb);
                    cnt=1;
                    base = word;
                }

                //끝 단어까지 붙여줘야함
                if(j == s.length()/i - 1) doCompression(base, cnt, sb);
            }

            //묶음으로 나눌 때 홀수개로 끊긴다면 -> 뒤에 남은 부분 붙여주기
            if(check && s.length() % i != 0) {
                sb.append(s.substring(idx, s.length()));
            }
            answer = Math.min(answer, getWordLength(sb));
        }

        return answer;
    }
    
    private static int getWordLength(StringBuilder sb) {
        return sb.length();
    }

    private static void doCompression(String base, int cnt, StringBuilder sb) {
        if(cnt <= 1) {
            sb.append(base);
        }

        else {
            sb.append(cnt);
            sb.append(base);
        }
    }
}

 

[큰 수 만들기]

 

* 로직

• number의 길이 - k는 구하고자 하는 답의 자리수이다
• 그렇다면 구하고자 하는 자리수의 왼쪽부터 마지막 일의 자리 수까지 가장 큰 수를 채워나간다
• 자리수를 하나씩 옮길때마다 가장 큰 수를 찾은 index의 다음 부분부터 그 다음 탐색을 진행한다

 

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int size = number.length() -  k;

        int idx=0;	//자리수마다 큰 수를 찾은 인덱스
        StringBuilder sb = new StringBuilder();
        
        //찾고자 하는 자리수의 왼쪽부터 마지막 일의 자리까지
        for(int i=size; i>=1; --i) {
            int max = 0;
            for(int j=idx; j<number.length()-i+1; ++j) {
                if(max < number.charAt(j) - '0') {
                    max = number.charAt(j) - '0';
                    idx = j+1;
                }
            }
            sb.append(max);
        }

        return answer = sb.toString();
    }
}