[프로그래머스/Level2] 문자열 압축 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 문자열

1. 압축할 문자열을 정한다. → String prev = s.substring(0, i)

2. 설정된 길이만큼 문자열을 잘라 인덱스를 이동하며 탐색한다. (j += i) 

  - 현재 위치에서 자를 문자수를 더한 (j+i) 마지막 인덱스가 문자열 길이를 벗어난다면, 문자열 길이로 설정한다. → int endIdx = Math.min(j + i, s.length());

  - 이전 문자열을 데려와 현재 자른 문자열과 비교한다.

        - 둘이 같다면, 자를 문자 수를 +1해준다.

        - 둘이 다르다면, 규칙을 벗어난 것이다. (자를 문자 수가 2 이상이면 그 수를 결과 문자열에 더하고, ) 해당 문자열을 붙이고, 방금 붙인 문자열을 새 압축 문자열로 등록하고, 자를 문자 수도 1로 재설정한다.

if(len >= 2) {
    result.append(len);
}
result.append(prev);
prev = nextStr; // 방금 붙인 문자열을 새로운 압축 문자열로 등록
len = 1;        // 압축 갯수 초기화

 

 

3. 압축 완료된 문자열의 길이를 구해 최솟값을 구한다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(String s) {
        int answer = s.length();
        int len = 1;
        
        for(int i = 1 ; i <= s.length()/2 ; i++) {  // 압축시킬 길이
            StringBuilder result = new StringBuilder(); // 새로 만들 문자열
            String prev = s.substring(0, i);    // 비교용 이전 문자열
            
            for(int j = i ; j <= s.length() ; j += i) {
                int endIdx = Math.min(j + i, s.length());   // 자르는 범위의 마지막 인덱스 처리
                
                String nextStr = s.substring(j, endIdx);
                
                if(prev.equals(nextStr)) {  // 이전 문자열과 현재 문자열이 같은 경우
                    len++;
                }
                else { // 새로운 문자열이 등장한 경우
                    if(len >= 2) {
                        result.append(len);
                    }
                    result.append(prev);
                    prev = nextStr; // 방금 붙인 문자열을 새로운 압축 문자열로 등록
                    len = 1;        // 압축 갯수 초기화
                }
            }
           result.append(prev);    // 마지막 남는 문자열 추가
            answer = Math.min(answer, result.length());
        }
        
        return answer;
    }
}
 

 

 

 

---

💦 어려웠던 점

- 단순하게 문자열에 따라 순서대로 진행하자... 처음에 Map 쓸 생각하고 난리도 아니었음(?)

- 문자열 길이를 1부터 최대 어느 길이까지 잘라 압축시킬지 정하지 못 했다. → 문자열 길이의 절반까지 잘라야 한다. 그래야 2번 이상 반복 가능

- 이전 문자열과 비교하면서 진행해야겠다는 생각은 들었는데 같거나 다를 때 어떻게 처리해야할지까지는 생각하지 못 했다.

 

1회독	2회독	3회독	4회독	5회독
V	240512	240630

 

 

 

(+240630 2회독)

import java.util.*;
 
class Solution {
    public int solution(String s) {
        int len = s.length();
        int answer = len;
        
        for(int i = 1 ; i <= len/2 ; i++) { // 압축시킬 길이
            int cnt = 0;
            String result = ""; // 결과 문자열
            String target = s.substring(0, i);  // 비교용 이전 문자열
            
            for(int j = 0 ; j <= len ; j += i) {
                String next = s.substring(j, Math.min(j+i, len));
                
                // 이전 문자열과 현재 문자열이 같은 경우
                if(next.equals(target)) {
                    cnt++;
                }
                // 새 문자열이 나온 경우
                else {
                    if(cnt >= 2) {
                        result += cnt;
                    }
                    result += target;
                    
                    target = next;  // 새로운 압축 문자열 등록
                    cnt = 1;    // 압축 갯수 초기화
                }                
            }
            
            // 마지막 남는 문자열 추가
            if(cnt >= 2) {
                result += cnt;
            }
            result += target;
            
            answer = Math.min(answer, result.length());
        }
        
        return answer;
    }
}

---

(참고)

[프로그래머스] 문자열 압축 (Java)

[프로그래머스] 문자열 압축(Java)