[프로그래머스] Level.2 - 문자열 압축(JAVA)

문제 설명과 제한사항

문제 간략 설명 

문자열 s 가 주어짐. s 를 i개로 잘랐을때 연속으로 나오는 문자열은 합칠 수 있다. ex) aaaabb 를 1개 단위로 자르면 a,a,a,a,b,b -> 4a2b로 합칠 수 있음      -> 2개 단위 2aabb 이렇게 압축을 할때 1개 이상 단위로 문자열을 잘라서 압축여 표현한 문자열중 가장 짧은 것의 길이를 반환.

풀이

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = s.length();
        List<Integer> list = new ArrayList<Integer>();
        if(s.length() == 1) return 1;
        String tmp1, tmp2;
        for(int i = 1; i <= answer/2 ; i++){
            boolean continuity = false;
            int len = answer;
            
            for(int j = i; j < answer ; j += i ){
                if (j >= answer - i) tmp1 = s.substring(j);
                else tmp1 = s.substring(j,j+i);
                tmp2 = s.substring(j-i,j);
                if(tmp2.equals(tmp1) && continuity){
                    len = len - i;
                }
                else if(tmp2.equals(tmp1) && !continuity){
                    len = len - i + 1;
                    continuity = true;
                }
                else continuity = false;
            }
            list.add(len);
        }
        Collections.sort(list);
        return list.get(0);
    }
}

++

우선 실패~

내가 생각한 방식은 다음과 같음.

처음으로 문자열의 길이를 len에 저장~

그리고 우선 substring 으로 문자열을 i개씩 자를 것임

-> 지금 자른것과 이전에 자른것이 같다면? : len - i + 1 (i만큼 짧아지고 앞에 숫자가 들어가서 +1)

-> 근데 이전에 자른것과 그 이전에 자른것이 같다면? : len - i (앞에 숫자는 바뀌고 i만큼 짧아짐.)

-> 그리고 list에 len 추가

-> len 정렬

-> 0번 리턴~

 

알고 있지만 간과한 것. : 우선 숫자가 10 이상이 되면 ++가 되어야 함.. boolean을 int로 바꿔볼까함.

 

++ 2차 풀이

import java.util.*;
class Solution {
    public int solution(String s) {
        List<Integer> list = new ArrayList<Integer>();
        if(s.length() == 1) return 1;
        String tmp1, tmp2;
        
        for(int i = 1; i <= answer/2 ; i++){
            int continuity = 0;
            int len = s.length();
            
            for(int j = i; j < answer ; j += i ){
                if (j >= answer - i) tmp1 = s.substring(j);
                else tmp1 = s.substring(j,j+i);
                tmp2 = s.substring(j-i,j);
                if(tmp2.equals(tmp1)){
                    if(continuity > 0 && continuity%10 != 0) len = len - i;   
                    else len = len - i + 1;   
                    
                    continuity++;
                }
                else continuity = 0;
            }
            list.add(len);
        }
        Collections.sort(list);
        return list.get(0);
    }
}

continuity 를 int 형으로 바꿔서 코드를 정리해 봄..

자리수가 넘어가면 +1을 해줬음! 이라고 생각했지만 10, 20, 30 다 +1 씩 되긴함. 고쳐야함

그래도 점수는 올랐음!

 

 

 

 

+++++ 3차풀이

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = s.length();
        int slength = s.length();
        if(slength == 1) return 1;
        String tmp;
        
        for(int i = 1; i <= slength/2 ; i++){
            int count = 0;
            int len = slength;
            for(int j = i; j < slength ; j += i ){
                if (j >= slength - i) tmp = s.substring(j);
                else tmp = s.substring(j,j+i);
            
                if(tmp.equals(s.substring(j-i,j))){
                    if(count > 0 && (count != 10 && count != 100 && count != 1000) ) len = len - i;   
                    else len = len - i + 1;   
                    count++;
                }
                else count = 0;
            }
            answer = Math.min(answer, len);
        }
        return answer;
    }
}

코드 다듬고 조건 추가해서 정리하고

list 쓰는건 낭비인거 같아서 그냥 answer을 넣고 최소값을 계속 최신화 하는 방식으로 바꿨다

근데

ㅋㅋㅋ ㅅㅂ 이번에도 2개의 테스트케이스가 말썽이네

 테스트 2 테스트 20 왜 하필 또 2랑 20이야 2랑 뭔 웬수 졌나 진짜 열 너무 받음~

 

 

보통 다른 사람들은 문자열을 새로 만들어서 문자열의 길이를 비교한다.

근데 그렇게 하면 뭔가뭔가 코드가 복잡해질 것 같아서 싫다고.

우선 오늘은 여기까지하고 다음에 다른 사람들 코드처럼 문자열로 비교를 하든가 해야겠다 열받는다.

 

+++

최종 풀이

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = s.length();
        if(answer == 1) return 1;
        
        for(int i = 1; i <= s.length()/2 ; i++){
            int count = 1;
            String sol = "";
            String tmp = "";
            
            for(int j = i ; j < s.length() ; j += i ){
                if (j + i > s.length()) tmp = s.substring(j);
                else tmp = s.substring(j , j + i);
            
                if(tmp.equals(s.substring(j - i,j))){
                    count++;
                }
                else {
                    if(count != 1){
                        sol += count + s.substring(j - i,j);
                        count = 1;
                    }
                    else sol += s.substring(j - i,j);
                }
            }
            if(count != 1) sol += count + tmp;
            else sol += tmp;
            
            answer = Math.min(answer, sol.length());
        }
        return answer;
    }
}