알고리즘) 카카오 블라인드 채용 2020, 문자열 압축

Kakao Blind Recruitment 2020

문자열 압축

프로그래머스

 

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

 

풀이

(2020.05.01)

 

문자열을 제일 앞부터 정해진 길이만큼 자르는게 중요해서 저 조건만 따로 적어봤다. 처음 문자열 부터 자르는 것과 중복되는 문자열의 갯수를 파악하는 것에 주의한다면 어려운 문제는 아니었다.

 

1. 자를 문자열의 길이만큼 loop를 돌렸다. (1~전체 문자열 길이의 절반, 편의상 n이라 칭하겠다)

2. 첫번째 Index부터 n만큼 자른 문자열을 저장해놓고, n~2n까지 문자열을 잘라 같은지 비교한다.

3. 같다면 카운트를 증가시켜 몇개의 자른 문자열이 중복되는지 저장한다.

4. 이 전 글자와 같지 않다면 중복된 문자열 길이를 변환하여, 줄어든 글자 수 만큼 전체 문자열 길이에서 빼준다.

5. 마지막까지 문자열 중복이 이어진 경우를 위해, 검사 후 줄어든 글자 수 만큼 전체 길이에서 빼준다.

 

---

(2020.06.05)

 

첫번째로 푼 방식과 비슷하게 풀었다. 전체 문자열 길이/2 ~ 1 까지 문자열을 제일 앞부터 탐색해서 카운트를 세주면서 글자를 줄여나갔을 때, 최소값이 되는 값을 저장했다. 저번 풀이에서는 String.ValueOf로 길이를 구했다면, 이번에는 반복문을 통해 10^n승보다 작은 값에대해 찾아주어 길이를 구해줬다. 또 차이점이 있다면, times를 사용하지 않았다는 것 정도가 되겠다.

 

코드 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Problem1_2019 {
    static int reduceLen(int cnt, int div) {    // 글자 줄어든 만큼 반환
        return div*cnt - (String.valueOf(cnt).length() + div);  // 원래 길이 - 바뀐 길이
    }

    static int solution(String s) {
        int len = s.length();   // 전체 길이
        int answer;
        int min = 1001;         // 1~1000자리의 문자열이기 때문에 최솟값은 최대보다 1 큰 1001로 설정

        int cnt=1;  // 중복된 횟수 카운팅

        if(len <=2) {
            return len;
        }

        for(int div =len/2; div >0; div--) {     // 문자열 자를 길이만큼 절반 ~ 1까지
            answer = len;   // 답 초기화
            String tmp = s.substring(0, div);   // 첫번째 인덱스부터 길이만큼 자르기

            for (int times = 1; times <= len / div; times++) {   // 100잔데 2개로 자르면 50개를 비교해야하기 때문.
                if(div*(times+1) > len) {   // 최대 글자 넘어가는 경우는 check 안함
                    break;
                }
                String dest = s.substring(div * times, div + div * times);  // next 문자열

                if (tmp.equals(dest)) {  // 전에랑 글자 같아?
                    cnt++;              // 횟수 증가
                } else {    // 여러번 중복되는 것 체크
                    if (cnt != 1) {   // 현재까지 중복된 갯수만큼 글자 줄여주기
                        answer -= reduceLen(cnt,div);   // 줄어든 글자 수 만큼 빼주기
                        cnt = 1;         // 중복 체크 횟수 초기화
                    }
                }

                tmp = dest; // 비교 글자 바꾸기
            }

            if (cnt != 1) { // 검사 끝나고 잔여 횟수가 남아있으면
                answer -= reduceLen(cnt,div);   // 줄어든 글자 수 만큼 빼주기
            }

            min = min > answer ? answer : min;
            cnt = 1;
        }
        answer = min;

        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String inStr = br.readLine();
        System.out.println(solution(inStr));
        br.close();
    }
}

 

코드 2

 

class Solution {
    public int solution(String s) {
        int len = s.length();
        int answer = len;
        if(answer >2) { // 길이 2 이하는 의미가 없음
            for(int letters=len/2; letters>0; letters--) {
                int cnt =1;
                int convertLen = len;
                String prev = s.substring(0,letters);
                for(int i=letters; i<=len-letters; i+=letters) {  // 시작점
                    String now = s.substring(i,i+letters);
                    if(now.equals(prev)) {  // 같은 경우
                        cnt++;
                    } else { // 다른 경우
                        if(cnt !=1) { // 줄여줘야함
                            convertLen -= reduceNum(cnt,letters);
                            cnt=1;
                        }
                    }
                    prev = now;
                }
                if(cnt !=1) {
                    convertLen -= reduceNum(cnt,letters);
                }
                answer = Math.min(convertLen,answer);
            }
        }
        return answer;
    }
    
    private int reduceNum(int cnt, int len) {
        int result = len*cnt;
        for(int i=1; i<=5; i++) { // 숫자 길이
            if(cnt < (int)Math.pow(10,i)) {
                cnt = i;
                break;
            }
        }
        len += cnt;
        return result-len;
        
    }
}