본문 바로가기
Algorithm

[알고리즘] [2020 카카오 블라인드] 문자열 압축

by byeongoo 2021. 1. 18.

1. 문제

2. 나의 풀이

처음에 리스트에 단어를 넣지 않고 현재 단어와 다음 단어를 구해서 풀려고 했더니 인덱스를 벗어나는 등의 엄청난 시간 낭비가 있었다. 비효율적이지만 푸는게 우선이니 스트링 리스트를 먼저 하나 선언하고 리스트에 단어를 집어 넣는데, 마지막 단어의 경우는 남은 단어를 모두 넣도록 처리했다.

 

리스트에 넣은 단어가 현재 인덱스의 단어와 뒤의 단어를 비교해서 같을 경우 몇개가 같은지 개수를 세어 주었고, 같지 않은 경우는 count가 1일 경우와 1보다 클 경우로 나누어서 문자열 앞에 숫자를 붙여줄지 안붙여줄지를 정하였다.

 

그리고 마지막 단어의 경우는 마지막 단어와 그 앞의 단어가 같은 경우와 같지 않은 경우로 구분하여 숫자를 붙여줄지 안붙여줄지를 정하였다.

import java.util.*;

class Solution {

    public int solution(String s) {

        int min = s.length();

        for(int i=1;i<=s.length();i++){
            List<String> list = new ArrayList<>();

            //list에 i만큼 나눠서 넣음
            for(int j=0;j<s.length();j+=i){
                int start = j;
                int end = start+i;
                String word = end>=s.length() ?  s.substring(start) : s.substring(start, end);
                list.add(word);
            }

            String compressed = "";
            int count = 1;
            for(int t=0;t<list.size();t++){ //앞에 문자와 뒤의 문자가 같은지 검사
                if(t == list.size()-1){ //마지막 단어의 경우

                    if(count == 1)
                        compressed += list.get(t);
                    else{
                        compressed += String.valueOf(count) + list.get(t);
                    }

                } else if(list.get(t).equals(list.get(t+1)))    //앞에 단어와 같은 경우
                    count++;
                else{   //앞과 뒤의 단어가 다른 경우
                    if(count == 1)
                        compressed += list.get(t);
                    else {
                        compressed += String.valueOf(count) + list.get(t);
                        count = 1;
                    }
                }
            }

            if(min>compressed.length())
                min = compressed.length();
        }

        return min;
    }

}