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

ynoolee·2021년 6월 24일
0

코테준비

목록 보기
19/146

문제

  • 문자열에서 같은 값이 "연속"해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있다.
  • 그 문자의 개수와 반복되는 값으로 표현 —> "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)
  • 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점—→ 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않음.
  • 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다. —> "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법
    • "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법 . (abc abc dede . 즉 dede 처럼, 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 된다)
  • 문제에서 구하라고 하는 것 : 압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성

문제 이해가 잘 안된 것 같으니 예시를 보자.

  • abcabcdede 는 길이가 10이다.

    < 이해 해보자 >

    • n을 3이라고 한다면 0 , 3, 6, 9에서 확인한다.
    • i+n > s.length 이면 Stop 하고 s.length-i 을 하면 단위로 잘리지 않고 [ 남은 문자열 ]의 길이를 의미한다.
  • "aabbaccc" —> 2a2ba3c

  • "ababcdcdababcdcd" —>

    • 만약 2개 단위로 잘라 압축 시, 오히려 숫자로 인해 길이가 더 길어진다. 2ab2cd2ab2cd —> 12
    • 반면 8개 단위로 잘라 압축 시, 2ababcdcd 로 —>9
  • "xababcdcdababcdcd" —> 이 예제를 통해 헷갈리던 부분을 해결함

    • 헷갈리던 것 : n개 단위인 경우, x에서 n개인 문자열이 연속하여 반복되는 게 없으면, 여기서 index를 1 증가시켜, a부터 n개를 보는 식인가 ? —> NO
    • 항상 n개 단위로만 성공하고 실패한다. 즉, 맨 처음부터 n개를 보고, 반복이 아니라면, i+n 위치의 것을 확인한다. i+1위치의 것을 확인하는게 아니다.
  • n 개 단위로 자른다고 한다면 idx?

    • i에서 반복이 일어나는지 확인한다.
      • HOW????
      • 예를들어 abab인 경우, 2개단위라하면 n=2이고, i=0일 때는, i+n 에서 ab가 있어야 —> 연속하여 반복이라 할 수가 있다.
    • n 개 단위로 매 번 앞의 것과 반복인지를 확인한다. 반복이 아니면, 앞의 문자열을 그대로 두고(결과 문자열의 길이에, n을 더한다. ),
    • 언제까지 ? i + n 이 s.length보다 작을 때 까지.

문제 해결

  • 걍 단순하게 생각나는 것

    • 길이가 1000이하이기 때문에, 완전탐색을 하더라도 괜찮을 것 같다.
      • 단위 n 을 1부터 n까지 전체 탐색
    • 그리디하게 풀어야 할까 ????
    1. 반복되는 문자열 중 " 가장 길이가 긴 것"

    2. 문자열의 "반복되는 수가 가장 많은 것 "

      아 이 방식은 아니다. 그저 완전탐색을 해야 할 것 같다.

    • 문제에서 오해하지 말아야 할 것. "n개"단위로 문자열을 자른다고 하면, n개 이외의 단위로는 자를 수 없다. 예를들어 위에서 예시를 든 것도, 3개 단위로 문자열 자르는 경우 2개로도 자를 수 있음에도 2개로 자를 수 있는 것은 배제 시켰다.
  • 사용할 String class의 메소드 에 대한 고민

    • substirng?
      • 일단 아주 단순하게(그리고 효율이 안나게) 매번 String생성하기.
  • 먼저 특정 문자열이 "연속해서 반복되는 횟수" 를 구하는 메소드 작성

    • 특정 문자열이 "연속해서 반복하는가"를 찾기
    • 몇 번 반복하는지 찾기
    1. str.substr(i,i+n)

    2. update i= i +n

    3. str.substr(i,i+n) 과 같은지를 확인.

      public int checkRepeat(String s, int idx,int n){
      	// 기준은
      	String target = s.substr(idx,idx+n);
      	int cnt =0;
      	// 반복한다. 
      	int i = idx+n;
      	while(i+n<=s.length){
      		String cur = s.substr(i,i+n);
      		if(cur.eqauls(target)) cnt++;
      		else break;
      	}
      	return cnt; 
      }
      	
    • 여기서 return 한 값 x n 만큼 한 곳부터 다음 idx가 되는 것.
class Solution {
    public int min = Integer.MAX_VALUE;

    public int solution(String s) {
        int answer = 0;
        int len = s.length();
        int totCnt =0; // 전체 문자열의 길이를 기록한다.
        int curCnt =0; // 현재 문자열의 반복횟수를 기록한다.
        // 모든 경우에 대한 탐색을 시행한다.

        for(int n =1; n<=len;n++){
            totCnt =0;
            int startIdx=0;
            while(startIdx+n<=s.length()){
                curCnt = checkRepeat(s, startIdx, n);
                startIdx+=n*curCnt;
                totCnt+=n;
                // 반복 된 경우, 반복 횟수도 길이에 더해줘야한다. 1이면 1, 11이면 2, 111이면 3을 더해줘야 한다.
                if(curCnt>1) totCnt+=String.valueOf(curCnt).length();
            }
            // 남은 길이를 더해줘야 한다. 예를들어 예제 3번 처럼."abcabcdede"의 경우, idx 9의 경우 9 + 3 >10 이기 때문에, while문을 벗어난다.
            // "e" 에 해당하는 길이를 더해줘야한다.
            totCnt += (s.length()-startIdx);
            if(totCnt<min) {
                min = totCnt;
            }
        }
        answer = min;
        return answer;
    }
    // idx부터 idx+n 까지의 문자열이 반복되는지 구한다.
    // 리턴 값이 1인 경우 --> 반복이 없다 .
    // 리턴 값이 1보다 큰  경우 --> 반복하는 횟수가 리턴된다.
    public int checkRepeat(String s, int idx, int n){
        if(idx+n>s.length()) return 1;
        String target = s.substring(idx,idx+n);
        int cnt = 1;
        int i = idx+n;
        while(i+n<=s.length()){
            String next = s.substring(i,i+n);
            if(next.equals(target)) {
                i+=n;
                cnt++;
            }
            else break;
        }
        return cnt;
    }
}

자리수 구하기 다른 방법

  • 다른 분의 풀이를 보니 Math.log10(..)을 사용하셨다.
  • 이 문제에서는 abcabc의 경우 --> 2abc가 된다. 여기서 "2"도 압축결과문자열의 길이에 포함되기에 이를 구하기 위해 나는
int len = String.valueOf(length);

를 하였는데 생각해보면
log10(111) 의 경우 2 가 나온다. 그러니 여기다 1만 더해주면 됨
log10(9) + 1 은 1이니 한 자리 수 라는게 맞다.

int len = Math.log10(length)+1;

0개의 댓글