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

💡문제

[level 2] 문자열 압축 - 60057

문제 링크

성능 요약

메모리: 82.9 MB, 시간: 31.44 m

---

 

🤔접근법

문제 요약

• 주어진 문자열을 규칙에 따라 압축했을 때 가장 짧은 문자열의 길이를 출력
• 문자열을 1개 ~ n개 단위로 잘라서 제일 앞에서부터 부분문자열을 보는데 특정문자열이 반복되면 반복횟수+문자열 로 압축 가능하다
• ex) abcabc → 3abc , abcabcdede → 3abcdede (길이가 3으로 잘랐을때, de는 반복 되긴 하지만 길이가 3이 아니라 압축할 수 없다.)
• 단 , 문자열은 제일 앞에서부터 정해진 길이로 자른다.

범위 체크 및 시간복잡도 예상

• 1 ≤ 주어지는 문자열의 길이 ≤ 1,000
• $O(N^2)$ 까지도 쌉가능
• 시간복잡도가 null~null~한 아주 착한 문제

풀이법

⭕ 접근 방법. 완탐

🔑 1 ~ (문자열 길이 절반) 까지 길이로 모두 잘라보고 압축해서 길이가 제일 짧은 걸 찾자.

1. 문자열을 자를 길이를 정한다. 1 ~ 문자열길이의 절반까지 잘라본다. ( 문자열 길이 절반 이상은 볼 필요가 없다. 반복될 수 없기 때문)
2. 부분 문자열을 지정한다. ( 부분 문자열은 반복되는 문자열인지 확인할 문자열을 의미하자. 만약 길이를 3단위로 잘라서 볼 차례라면 부분 문자열은 인덱스 0 ~ 2 | 3 ~5 | 6 ~ 8 …차례로 반복된다. )
3. 부분 문자열을 기준으로 다음 부분 문자열이 반복되는지 확인한다. (예를 들어 부분 문자열이 3 ~5 라면 6 ~ 8 부분 문자열이, 9 ~ 11 부분문자열이 동일한 지 판별한다. )
4. 만약 반복 된다면 반복횟수 변수를 +1 하고 그 다음 부분 문자열을 본다.
5. 만약 반복 되지 않는다면 반복 횟수를 세는 것을 멈추고 압축된 문자열을 저장할 문자열 변수에 횟수 + 부분문자열을 저장한다.
6. 반봇횟수 변수를 초기화 하고 다음 부분 문자열로 변경한다.
7. 반복하고 남은 문자가 있다면 뒤에 붙여 압축된 문자열을 완성한다.
8. 문자열을 끝까지 다 봤다면 자를 문자열의 길이를 +1 증가시켜 위 과정을 반복한다.
9. 가장 짧은 압축된 문자열의 길이를 찾는다.

substring 시간복잡도 → $O(N)$

? 로직은 시간복잡도가 N^2 일 것이다. 다만 이중 반복문 안에 substring을 썼기 때문에 N^3 이라고 생각됐다

근데 왜 안터질까

➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$

 

 

---

😎SUCCESS

고냥 단박에 성공

너무 오랜만이여서 감격

---

👩‍💻 코드

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

class Solution {
    public int solution(String s) {
        // 입력 문자열의 길이를 answer로 초기화
        int answer = s.length();
        String zipStr;

        // 토큰 길이를 1부터 문자열 길이의 절반까지 반복 (문자열 절반까지만 확인하면 충분함)
        for (int tokenLen = 1; tokenLen <= s.length() / 2; tokenLen++) {
            zipStr = ""; // 압축된 문자열을 저장할 변수 초기화
            int start = 0; // 시작 인덱스 초기화
            int end = tokenLen; // 끝 인덱스는 토큰 길이만큼 설정
            String subStr = s.substring(start, end); // 첫 부분 문자열 설정

            // 다음 부분 문자열로 이동
            start += tokenLen;
            end += tokenLen;
            int cnt = 1; // 부분 문자열의 반복 횟수를 1로 초기화

            // 보고 있는 문자열의 범위가 입력 문자열을 넘어가지 않는 동안 반복
            while (end <= s.length()) {
                // 현재 부분 문자열과 다음 부분 문자열이 같으면 반복 횟수 증가
                if (s.substring(start, end).equals(subStr)) {
                    cnt++;
                } else { // 다르면 현재까지의 부분 문자열을 압축
                    zipStr = makeZipStr(cnt, zipStr, subStr);

                    // 범위를 벗어나면 반복 종료
                    if (end > s.length()) {
                        break;
                    }
                    // 새로운 부분 문자열 설정
                    subStr = s.substring(start, end);
                    cnt = 1; // 반복 횟수 초기화
                }
                // 다음 부분 문자열로 이동
                start += tokenLen;
                end += tokenLen;
            }

            // 남은 부분 문자열을 압축
            zipStr = makeZipStr(cnt, zipStr, subStr);

            // 단위만큼 나누고 남은 문자열 붙이기
            zipStr += s.substring(start);

            // 압축한 문자열의 길이와 현재 최소 길이 중 작은 값을 선택
            answer = Math.min(answer, zipStr.length());
        }
        return answer;
    }

    // 반복 횟수와 부분 문자열을 이용해 압축 문자열을 만드는 함수
    private static String makeZipStr(int cnt, String zipStr, String subStr) {
        // 반복 횟수가 1이 아닐 때만 반복 횟수를 추가
        if (cnt != 1) {
            zipStr = zipStr + cnt + subStr;
        } else {
            zipStr = zipStr + subStr;
        }
        return zipStr;
    }
}

99클럽 코딩테스트 준비 개발자 취업 항해99 TIL