99클럽 코테 스터디 4일차 TIL + Programmers 문자열 압축

1. 문제 설명

문제 링크

2. 접근 방식

1. 부분 문자열은 크기 1부터 N/2까지만 생각하면 된다. (N = 문자열의 길이)
   왜냐하면, 부분 문자열의 크기가 절반 이상이면 반복이 불가하므로, 세는 의미가 없다.

2. 1번에서 정한 문자열 크기만큼 처음부터 자른다.

   이 행위는 0 ~ N - i 까지만 반복한다. 부분문자열을 구하는 substring(startIndex, endIndex)에서 endIndex가 배열의 범위를 넘어가면 예외가 발생한다. 우리는 substring(startIndex, startIndex+i)만큼 항상 할 것이므로, endIndex가 배열의 범위를 넘어서지 않도록 반복의 범위를 위와 같이 정한다.
   최초 자른 부분 문자열은 중복 체크가 불가하므로 이전 문자열(이하 prev)에 저장한다.

3. 이전 문자열과 현 문자열을 비교하여 동일하면 반복횟수(이하 count)를 1 늘린다.

4. 동일하지 않으면 prev과 count를 답변 StringBuilder(이하 ans)에 삽입하고, count를 초기화 한다.

5. 현재 문자열을 prev에 대입한다. (이제 이전 문자열 이므로)

6. 2번의 반복문 이 끝나면, prev에는 항상 맨 마지막 부분 문자열이 저장되어있다. 해당 부분 문자열을 ans에 저장한다.

7. 만약 N%i != 0이면, 반복문을 끝나고도 확인하지 않은 나머지 값들이 존재한다는 것이다. 해당 값들은 반복문의 길이보다 작아 반복을 확인할 필요가 없으므로, 그냥 ans에 저장한다.

8. 1~7 이후에 나온 ans의 길이를 이전 ans의 길이와 비교하여 minimum이면 갱신한다.

3. 코드 분석

import java.io.*;
import java.util.*;

class Solution {
    public int solution(String s) { 
        int ans = Integer.MAX_VALUE;

        if(s.length() == 1) return 1; // 예외처리: 문자열의 길이가 1이면 밑에 모두 통과하기 때문

        for(int i = 1; i <= s.length()/2; i++){
            StringBuilder sb = new StringBuilder(); // 답변 저장용 StringBuilder
            String prev = ""; // 이전 문자열
            int count = 1;    // 반복 횟수
            for(int j = 0; j <= s.length() - i; j += i){
                String cur = s.substring(j, j+i); // 부분문자열을 자른다.
                if(cur.equals(prev)){ // 현재 자른 문자열이 이전과 같으면 count ++;
                    count++;
                }else {// 아니면, 이전 문자열의 지금까지 반복횟수와 함께 sb에 저장
                    sb.append(count>1 ? count : "").append(prev);
                    count = 1;
                }
                prev = cur; // 이전 문자열을 갱신
            }
            sb.append(count>1? count : "").append(prev); // 맨 마지막에 남은 부분 문자열 저장
            if(s.length()%i !=0){ // 나머지 값들 모조리 sb에 저장
                String last = s.substring(s.length() - s.length()%i, s.length());
                sb.append(last);
            }
            ans = Math.min(ans, sb.toString().length()); // minimum 문자열 길이 갱신
        }
        return ans;

    }
}

4. 성장 하기

1. 문자열 자르는 거를 항상 맨 처음 값을 시작점으로 시작 한다는 것을 문제를 끝까지 읽지 않아 파악하지 못했다.
   (예를 들어 xabcabc를 3씩 자른다고 치면, x / abc / abc 이렇게 못 자르고 항상 xab / bca / bc 이렇게 잘라야 함)
   문제를 끝까지 읽자!!!
2. substring을 잘 사용하지 않아서, 잘 몰랐다. 그 때문에, StringBuilder로만 일을 처리하려다 보니, 문제를 더 복잡하게 푼 것 같다. 그 때문에 큰 흐름은 맞았으나 끝끝내 못 풀었다.

String.substring(int endIndex);    // 처음부터 endIndex 직전까지의 부분 문자열을 반환
String.substring(int startIndex, int endIndex); // 시작점부터 endIndex 직전까지 문자열을 반환

모두 소문자로, substring이란 것을 유의하자... 나 계속 subString이라 적어서 틀렸다.