Programmers Lv2 k 문자열 압축 (JAVA)

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

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

문제는 다들 읽고 왔을 것이라 생각한다.

---

서문

여러가지 생각을 해보다

다음과 같은 방식으로 풀어보기로 했다.

 

        //1. int n = String 반띵값
        //2. n을 기준으로 String을 분리하여 전 후 비교
        // 2-1. 비교 가능(같은 값 존재) -> 그 개수 기준으로 잘라 min에 값 저장
        // 2-2. 비교 불가능(같은 값 존재 X) -> continue...
        //3. min 출력

 

String의 반의 길이를 구해 그것을 기준으로 하나씩 비교해보겠다는 생각이었다.

막상 구현하다보니, 너무 복잡해지고 3번 중복되는 경우를 어떻게 처리할지 고민하다

다른 블로그를 참고하여 해결했다. ↓

https://fbtmdwhd33.tistory.com/226

[프로그래머스,Level 2] 문자열 압축(JAVA 구현)

---

풀이

기본적인 방식은 내가 생각한 부분과 크게 다르진 않았다.

다만  substring(begin, end)을 활용하지 못했었다.

 

substring을 통해 문자열의 묶어서 비교해주면 된다.

예를 들어)

"abcabcdede" 가 주어진다고 생각해보자.

 

1. 문자열의 길이를 반으로 나누면, 5이다. 

   이 말은 압축할 수 있는 범위가 5보다 커질 수 없다는 것이다.

 

1부터 5까지 하나씩 비교해보면...

(1자리 압축)

a a
b ab
c abc
a abca
b abcab
c abcabc
d abcabcd
e abcabcde
d abcabcded
결과 = abcabcdede

 

(2자리 압축)
ab ab
ca abca
bc abcabc
결과 = abcabc2de

 

(3자리 압축)
abc 2abc
결과 = 2abcdede

 

(4자리 압축)
abca abca
결과 = abcabcdede

 

(5자리 압축)
abcab abcab
결과 = abcabcdede 

 

위와 같은 순서로 진행될 것이다.

이걸 코드로 구현하면...

public class Main {
    public static int solution(String s) {
        int answer = Integer.MAX_VALUE; // 최소 문자열을 찾기 위한 비교변수
        
        if(s.length() == 1) return 1; // 문자열의 길이가 1일 경우

        for(int i=1;i<=s.length()/2;i++){
            
            String str = ""; // 정답 문자열
            String temp = ""; //비교할 문자열
            int count = 1; //동일한 문자 개수

            for(int j=0; j<s.length()/i; j++){

                // 이전 문자열과 동일한지
                // ex) dedede인 경우 3번째 de
                if(temp.equals(s.substring(j*i, (j*i)+i))){
                    count++;
                    continue;
                }

                // 같은 문자일 경우
                // 앞을 숫자로 변경하여 str 붙임
                // ex) 3a
                if(count>1){
                    str += count + temp;
                    count = 1;
                }
                // 같은 문자가 아닐경우
                // 그냥 붙임
                else{
                    str += temp;
                }

                System.out.print(temp+" ");
                System.out.println(str);

                // temp에 비교할 문자열 저장
                temp = s.substring(j*i, (j*i)+i); 
            }

            // 마지막 temp에 저장된 문자열 붙임
            // 같을 경우
            if(count>1){
                str += count + temp;
                count = 1;
            }
            //같지 않을 경우
            else{
                str += temp;
            }

            // i 로 나눠떨이지지 않는 경우, 남은 부분 substring으로 붙이기
            if(s.length()%i != 0){
                str += s.substring(s.length()-s.length()%i, s.length());
            }

            System.out.println("str = "+str);

            // 기존 answer과 현재 str을 비교해  더 짧은 것 answer에 저장
            answer = answer > str.length() ? str.length() : answer;
        }

        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution("abcabcdede"));
    }
}

 위와 같은 방식으로 구현된다!