[프로그래머스] 문자열 압축 - Java [자바]

 

📜 문제 내용

 

 

🤔 과정

• 문제를 읽고, "중복된 문자열을 자른다" 를 통해 substring 이 생각났고, "문자열을 붙인다"에서 StringBuilder 가 생각났으며, "앞에서부터 중복되는 것을 확인하고 붙인다" 는 점에서 First In First Out 특징을 가진 자료구조인 Queue 가 생각났다. 
• 코드 과정을 구상할 때, 시간을 많이 잡아먹은 부분은 index 부분이었다. 
  1) unit을 어떤 범위로 가져가야 좋을지
  2) substring의 인덱스를 어떻게 지정하면 좋을지
• unit의 범위는 1글자부터 문자열 전체 길이까지 가는 것이 아니라, 문자열의 절반까지가 유의미한 최대 범위가 될 것이다. ex) abcdefabcdef => 2abcdef
• substring의 인덱스 범위는 for문의 증감식과 endIdx를 이용해서 정해주었다. 

 

 

✨ 최종 제출 답안

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

class Solution {
    public static String compressor(String str, int unit){
        StringBuilder sb = new StringBuilder();
        
        // 잘려진 문자가 먼저 나가는게 FIFO 인 Queue가 적합하다고 판단 
        Queue<String> q = new LinkedList<>();
        
        // 자르는 단위를 토대로 substring의 끝 인덱스를 지정
        // 자른 뒤 Queue에 넣기 
        for(int i = 0; i < str.length(); i += unit){
            int endIdx = Math.min(i + unit, str.length());
            q.offer(str.substring(i, endIdx));
        }
        
        while(!q.isEmpty()){
            int cnt = 1;
            String curr = q.poll();
            
            // 잘려진 현재 문자열과 같다면 cnt 1 증가 및 queue에서 버리기 
            while(!q.isEmpty() && q.peek().equals(curr)){
                q.poll();
                cnt++;
            }
            
            // 한번만 나타난 경우는 1을 생략하고 문자열 붙이기 
            if(cnt > 1){
                sb.append(cnt).append(curr);
            }else{
                sb.append(curr);
            }
            
        }
        
        return sb.toString();
    }
    
    public int solution(String s) {
        // 주어진 문자열의 길이 저장 및 최소 길이 초기화
        int sLen = s.length();
        int minLen = sLen;
        
        // 자르는 단위 i는 1글자부터 최대 (문자열 길이) / 2 이어야 유의미
        for(int i = 1; i <= sLen / 2; i++){
            String compStr = compressor(s, i);
            minLen = Math.min(minLen, compStr.length());
        }
        
        int answer = minLen;
        return answer;
    }
    
}

 

 

• 문자열을 잘라서 비교해야하는 문제라서 substring의 사용은 필수적인데, queue를 사용하든, stack을 사용하든, 완전탐색을 하든 다 가능할 것 같아보인다. 

 

 

🔗 문제 링크

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

프로그래머스