99클럽 코테 스터디 4일차 TIL / [프로그래머스] 문자열 압축

오늘의 학습 키워드

---

문자열 파싱

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 문자열 압축
• 난이도: Lv2

풀이

---

class Solution {
    public int solution(String s) {
        int answer = zipString(s);
        return answer;
    }
    
    public int zipString(String s) {
        int minLength = s.length();

        for(int splitLength=1; splitLength<=s.length()/2; splitLength++) {
            int equalCnt = 1;
            String leftStr = s.substring(0, splitLength);
            StringBuilder sb = new StringBuilder();
            
            // 가능한 압축 문자열 길이 순회
            for (int right = splitLength; right <= s.length(); right += splitLength) {
                // 압축 문자열 길이로 나눠지지 않는 경우를 고려
                int endIdx = Math.min(right + splitLength, s.length());
                String rightStr = s.substring(right, endIdx);
                if (leftStr.equals(rightStr)) {
                    equalCnt++;
                } else { // 다를 때마다 sb에 저장
                    if (equalCnt > 1) {
                        sb.append(equalCnt);
                    }
                    sb.append(leftStr);
                    leftStr = rightStr;
                    equalCnt = 1;
                }
            }

            if (equalCnt > 1) {
                sb.append(equalCnt);
            } 
            
            sb.append(leftStr);
            
            minLength = Math.min(minLength, sb.length());
        }

        return minLength;
    }
}

접근

• 가능한 압축 문자열 길이를 하나씩 고려해보며 가능한 모든 케이스를 구했습니다.
  • 첫 번째 for 문에서 범위를 길이 / 2로 지정한 이유
    • 문자열 압축이 가능한 경우는 최소 2개의 부분 문자열이 같은 경우입니다. 따라서, 길이 / 2 보다 큰 길이를 가질 수 없습니다.
• 보다 구체적으로, 초기에 leftStr 이라는 기준값을 잡고 압축 문자열의 길이만큼 문자열을 자른 rightStr과 계속 비교하면서 다를 때마다 StringBuilder에 저장하는 방식으로 구현했습니다.

소요 시간

1시간 30분

회고

---

left, right 두 개의 포인터를 한 칸씩 이동하며 가능한 압축 문자열을 찾는 문제로 착각했습니다… 😭
입출력 예시에 있는 조건을 보지 못해서 시간이 오래 소요됐네요.