2020 카카오 블라인드 채용 > 문자열 압축 문제풀이 - Java

안녕하세요 besforyou입니다.

 

2020 카카오 블라인드 채용 > 문자열 압축 문제 풀이입니다.

 

---

문제 풀이 

 

조건들이 다양하고, 복잡하고 마지막 원소나 첫 번째 원소 등의 edge case를 다루기가 까다로운 문제였습니다.

 

일반적인 배열을 이용하여 풀 수도 있겠지만 저는 stack 자료구조를 이용하였습니다. 

 

1. 문자열 단위 정하기

문자열 자르는 단위는 1부터 N/2까지 하면 됩니다. N/2 이상의 길이로 문자열을 잘라봤자 길이가 줄어들지 않으므로 N/2 이상의 단위로는 문자열을 압축할 필요 없습니다.

 

public int solution(String s) {
        int len = s.length();
        int min = 1001;
        for (int i = 1 ; i <=  ( len / 2 ) + 1  ; i++) {
            String compressed_str = compress(i, s);
            int newLen = compressed_str.length();
            if (min > newLen) min = newLen;
        }
        return min;
    }
 

 

2.  문자열 분리

정해진 단위에 맞게 문자열을 분리하여 배열에 저장합니다. 단, 문자열이 정해진 단위에 딱 맞게 분리되지 않는 경우를 생각해야 합니다. (ex : 길이 9인 문자열을 단위 4로 분리 )

 

 public String compress(int unit, String str) {
        int len = str.length();
        int idx = 0;
        Integer count = 0;
        int unit_count = len / unit;
        if ( len % unit != 0 ) unit_count += 1;        // 문자열이 단위 길이에 나누어떨어지지 않을 경우
        String [] units = new String[unit_count];
 
        while (idx < len) {
            String token = "";
            for (int i = 0 ; i < unit && idx < len; i++) {
                token += str.charAt(idx);
                idx += 1;
            }
            units[count++] = token;
        }
 
 

 

3. 조건에 맞는 작업

정해진 단위로 나뉘었을 때 이어지는 문자열 단위들의 개수를 세고 이전 문자열 단위와 다른 문자열이 있을 때 개수와 이전 문자열 단위를 붙이는 방식으로 문자열을 압축하면 됩니다. 이 작업을 수행할 때 stack을 사용하면 매우 편리합니다.

 

        count = 0;
        String ans = "", cur;
        Stack<String> stack = new Stack<>();
        for (int i = 0 ; i < unit_count ; i++) {
            cur = units[i];
            if ( stack.isEmpty() == true ) stack.push(cur); // 스택이 비어있다면 push
            else {  // 비어 있지 않은 경우
                if (stack.peek().equals(cur)) stack.push(cur); // 현재 참조중인 문자열 단위가 있다면 push
                else { // 이전 문자열 단위와 다른 문자열 단위를 참조중인 경우
                    Integer size = stack.size();
                    if (size > 1 ) ans += size.toString();  // 겹치는 문자열 단위가 있다면
                    ans += stack.peek();
                    stack.clear();
                    stack.push(cur);
                }
            }
        }
// 스택 속 남은 문자열 단위 이어붙이기
        Integer size = stack.size();
        if (size > 1 ) ans += size.toString();
        ans += stack.peek();
 

 

코드

 

import java.util.Stack;
 
class Solution {
    public int solution(String s) {
        int len = s.length();
        int min = 1001;
        for (int i = 1 ; i <=  ( len / 2 ) + 1  ; i++) {
            String compressed_str = compress(i, s);
            //System.out.println(compressed_str);
            int newLen = compressed_str.length();
            if (min > newLen) min = newLen;
        }
        return min;
    }
 
    public String compress(int unit, String str) {
        int len = str.length();
        int idx = 0;
        Integer count = 0;
        int unit_count = len / unit;
        if ( len % unit != 0 ) unit_count += 1;
        String [] units = new String[unit_count];
 
        while (idx < len) {
            String token = "";
            for (int i = 0 ; i < unit && idx < len; i++) {
                token += str.charAt(idx);
                idx += 1;
            }
 
            units[count++] = token;
        }
 
        count = 0;
        String ans = "", cur;
        Stack<String> stack = new Stack<>();
        for (int i = 0 ; i < unit_count ; i++) {
            cur = units[i];
            if ( stack.isEmpty() == true ) stack.push(cur);
            else {
                if (stack.peek().equals(cur)) stack.push(cur);
                else {
                    Integer size = stack.size();
                    if (size > 1 ) ans += size.toString();
                    ans += stack.peek();
                    stack.clear();
                    stack.push(cur);
                }
            }
        }
 
        Integer size = stack.size();
        if (size > 1 ) ans += size.toString();
        ans += stack.peek();
 
        stack.clear();
        return ans;
    }
}