프로그래머스 (카카오 기출) | LV.2 문자열 압축 - 문자열 활용 구현 문풀 (Java)

⬛ 프로그래머스 (카카오 기출) | LV.2 문자열 압축 - 문자열 활용 구현 문풀

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

프로그래머스

문제 설명

---

💚문제 접근 방식

처음에는 절반까지만 자르면 되지 않을까 생각했는데, 마지막 케이스의 경우 17글자인데도 결국 더 짧게 압축하는 방법이 없어서 17을 반환한 것을 보고 split 단위를 전체 글자 수 까지 하나씩 늘려가며 푸는 것으로 마음을 굳혔다.

s 글자수가 최대 10^3이라서 이중for문 돌아도 10^6이고, 이 경우 백만 정도라 괜찮다고 생각됐기 떄문이다.

[1차 생각]

처음 든 생각은 1글자 ~ 전체 글자 단위로 자르면서 자른 문자열을 HashMap에 중복없이 카운팅하고 → 압축 문자열 구성하면 되지 않을까 ? 생각했다.

→ 하지만 이건 안된다. 연속된 문자의 경우만 카운팅하는데 hashMap은 불연속적인 중복값도 카운팅하므로 그렇다. 따라서 다른 방법을 활용하려고 생각헀다.

[2차 생각] : List에 담고, for문 돌면서 연속된 String 카운팅하며 압축문자열 생성하자.

(1) 1글자 ~ 전체 글자 단위로 늘려가며 잘라서 List<String>에 담아 반환하는 함수

→ 이 함수에서 List<String>에 각각의 단위로 substring 잘린 문자열을 담을 거다.

(2) List<String> 을 순회하면서 연속된 중복값에 대해 압축하여 글자수 반환하는 함수

→ 이 함수는 List에 담긴 String을 순회하면서 직전 문자열과 같은 문자일 경우 ++처리해주고

→ 직전 문자열과 다른 문자열일 경우 ‘압축 문자열’을 생성한다.

주의할 점은 (직전과 다른 경우) 문자열을 이어붙여 압축하는 작업을 하고 있기 때문에 필연적으로 마지막 문자열은 반복문 나와서 이어붙여야 정상 세팅이 된다.

---

💚 제출 코드

import java.util.ArrayList;
import java.util.List;

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

        for (int length = 1; length <= s.length(); length++) {
            List<String> tokens = getSplitTokens(s, length);

            int compLen = getCompressedString(tokens);
            
            answer = Math.min(answer, compLen);
        }

        return answer;
    }

    private List<String> getSplitTokens(String s, int length) {
        List<String> tokens = new ArrayList<>();
        for (int startIndex = 0; startIndex < s.length(); startIndex += length){
            int endIndex = startIndex + length;
            if (endIndex > s.length()) {
                endIndex = s.length();
            }
            tokens.add(s.substring(startIndex, endIndex));
        }
        return tokens;
    }
    private int getCompressedString(List<String> list){
        String answer="";
        String tmp= list.get(0);
        int cnt =1;
        for(int i=1; i<list.size(); i++){
            if(tmp.equals(list.get(i))){
                cnt++;
            }else{
                if(cnt>1) answer += String.valueOf(cnt);
                cnt = 1;
                answer += tmp;
                tmp = list.get(i);
            }
        }
        //내가 다른 글자 나타날 때마다 answer에 누적해서 String을 합쳐주고 있기 떄문에
        //필연적으로 마지막 문자 종류는 (더 이상 자기와 다른 다음 문자가 없으므로) 붙이지 못하고 반복문을 탈출한다.
        //따라서 마지막 문자는 반복문에 나와서 처리해줄 필요가 있다.
        if(cnt > 1) answer += String.valueOf(cnt);
        answer += tmp;
        return answer.length();
    }
}

💚시간 복잡도

- 시간복잡도는 문자열 s 길이가 최대 1000이라서, 이중for문 돌아도 100만이다. 

💚회고

- 생각보다 문자열 처리하면서 시간을 많이 썼다. 이중for문 돌면서 바깥 i는 자르는 단위를 지칭하게 하고, 안쪽 j는 i만큼의 단위씩 늘려가며 String을 자르도록 하려고 헀는데, 이 점을 구현할 때 생각보다 애를 많이 먹었다. 문자열 처리하는 구현 문제도 은근 있기 때문에 해결하는 연습을 잘 해야할 것 같다.