[Java] 프로그래머스 - 문자열 압축 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

코딩테스트 연습 - 문자열 압축

 

 

 

 

 

import java.util.*;

class Solution {
    int answer = 0;
    public int solution(String s) {
        answer = s.length();
        for (int i = 1; i < s.length(); i++) {
            func(s, i);
        }
        
        return answer;
    }
    
    public void func(String s, int cut) {
        int position = 0;
        ArrayList<String> arr = new ArrayList<>();        
        
        // if (s.length() % cut != 0) return;
        
        while (position < s.length()) {
            int temp = (position+cut <= s.length()) ? position+cut : s.length();
            arr.add(s.substring(position, temp));
            position += cut;
        }
        
        String word = arr.get(0);
        StringBuilder sb = new StringBuilder();
        int number = 1;
        
        for (int i = 1; i < arr.size(); i++) {
            String temp = arr.get(i);
            
            if (temp.equals(word)) {
                number++;
            } else {
                if (number != 1) sb.append(number);
                
                sb.append(word);
                
                number = 1;
                word = temp;
            }
        }
        
        if (number != 1) sb.append(number);
        sb.append(word);
        
        // System.out.println(sb.toString() + ", " + sb.length());
        answer = Math.min(answer, sb.length());
        
    }
}

 

테스트 1 〉	통과 (0.10ms, 75MB)
테스트 2 〉	통과 (1.04ms, 77.9MB)
테스트 3 〉	통과 (0.73ms, 68.8MB)
테스트 4 〉	통과 (0.15ms, 69MB)
테스트 5 〉	통과 (0.03ms, 78.2MB)
테스트 6 〉	통과 (0.20ms, 86.9MB)
테스트 7 〉	통과 (1.01ms, 71.6MB)
테스트 8 〉	통과 (1.11ms, 73.6MB)
테스트 9 〉	통과 (2.04ms, 79.1MB)
테스트 10 〉	통과 (7.07ms, 74.7MB)
테스트 11 〉	통과 (0.41ms, 70.3MB)
테스트 12 〉	통과 (0.26ms, 71.1MB)
테스트 13 〉	통과 (0.46ms, 70.9MB)
테스트 14 〉	통과 (1.55ms, 76MB)
테스트 15 〉	통과 (0.28ms, 69.4MB)
테스트 16 〉	통과 (0.07ms, 80.1MB)
테스트 17 〉	통과 (2.26ms, 78.5MB)
테스트 18 〉	통과 (2.26ms, 75.8MB)
테스트 19 〉	통과 (2.18ms, 75.2MB)
테스트 20 〉	통과 (5.41ms, 79.5MB)
테스트 21 〉	통과 (6.29ms, 86.8MB)
테스트 22 〉	통과 (6.04ms, 74.2MB)
테스트 23 〉	통과 (4.74ms, 83.3MB)
테스트 24 〉	통과 (5.05ms, 84.8MB)
테스트 25 〉	통과 (5.94ms, 81.5MB)
테스트 26 〉	통과 (6.17ms, 85.6MB)
테스트 27 〉	통과 (6.64ms, 81.5MB)
테스트 28 〉	통과 (0.07ms, 75.2MB)

 

 

 

 

 

글자 자르는 것은 1글자부터 주어진 글자 s의 길이까지 1글자씩 늘려가면서 자르도록 for문으로 func함수를 호출.

 

 

그래서 substring()으로 글자를 잘라서 ArrayList에 넣고

앞에서부터 글자가 같은지 아닌지를 구분하고 같으면

만약에 글자가 같으면 같은 글자 개수 세는 것 (변수명 : number)에 +1,

다르면 StringBuilder에 number이랑 글자 추가 후 초기화.

 

 

 

 

그리고 for문이 끝나면 StringBuilder 길이랑 answer 길이 비교해서 작은 것 리턴으로 끝..

 

 

 

 

 

 

 

 

뭔가 예전엔 엄청 복잡하게 한 것 같은데.. 이번엔 비교적 쉽게 푼 것 같다.

 

예전에 풀었던 코드

 

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        
        for (int i = 1; i <= s.length() / 2; i++){
            int num = 1;
            
            int a = 0;
            if (s.length() % i != 0) a = 1;
            
            String[] data = new String[(s.length() / i) + a];
            
            for (int j = 0; j < data.length; j++){
                int start = j * i;
                int end = (j + 1) * i;
                
                if (end > s.length()) end = s.length();
                data[j] = s.substring(start, end);
            }
        
            int size = 0;
            for (int j = 0; j < data.length - 1; j++){
                String first = data[j];
                String second = data[j + 1];
                
                if (first.equals(second)){
                    num++;
                } else {
                    if (num == 1){
                        size += first.length();
                    } else {
                        size += first.length() + Integer.toString(num).length();
                    }
                    
                    num = 1;
                }
            }
            
            if (num == 1){
                size += data[data.length - 1].length();
            } else {
                size += data[data.length - 1].length() + Integer.toString(num).length();
            }            
            answer = Math.min(answer, size);
        }
        
        if (s.length() == 1){
            answer = 1;
        }
        
        return answer;
    }
}