[kakao & 프로그래머스] 문자열 압축 (solved: java, feat : python)

반응형
반응형

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

 

이 문제에 접근하기 위해서 생각보다 많은 시간이 소요 되었다.

이 문제는 문자열을 자르는 문제다.

[개요]

즉, 어떤식으로 문자열을 잘라야 하는지가 중요한다. 단순히 반복문을 돌려서 문자열을 자를수도 있지만

자바에는 substring이라는 메소드가 있다.

자바의 substring은 특정 위치부터 시작해서 원하는 갯수를 입력하면 그 결과 값이 리턴이 된다.

즉, abc에서 substring(0,2)를 했을 경우 (0번째 부터 2개니까 ab가 리턴 된다.

근데 자르는건 알겠는데.

얼마나 잘라야 하는지... 뭐를 잘라야하는지 아무 정보가 주어져있지 않아 보였다.

그래서 생각했다.

1개를 자를때는

0,1

2개를 자를때는

0,2

3개는

0,3

4개는

0,4 .... 쭉쭉

그러면 우리는 뒷자리가 바뀐다는 사실을 발견했다.

즉, 

for(int i = 1;i <s.length();i++) {
  String sub = s.substring(0,i);
}

로 하면 되는게 아닐까?

이렇게 구한다면

abcde로 위 코드를 돌리면 

a
ab
abc
abcd
abcde

로 차례로 리턴된다.

하지만 이걸로는 답을 풀기에는 적절하지 않아 보인다.

왜냐하면 이 방법은 맨 앞자리만 확인이 되기 때문이다.

그러면 문자열을 다시 자를 필요성이 있어보이는데

substring을 또 이용하면 되는 걸까?

근데 문제는...

substring을 어떤식으로 이용할 수 있을지가 의문이다.

왜냐하면 substring(step,?)로 해둘수는 있겠지만 이 렇게 하면

모든 잘라야 하는 범위를 확인이 불가능할 것 같다.

뭐 지금은 방법이 생각이 나지 않을 수도 있겠지만 말이다. (정답이 있을 수도 있겠다는 말)

그러면 이 다음부터는 substring으로 불가능하다는 가정하에 접근을 해보겠다.

위 substring에서 변수 값을 1부터 n까지 증가를 시키고 있다.

즉, 다른 잘라야 되는 값을 알기 위해서는 다시 반복문을 이용해야하는 것을 알 수 있다.

근데.. 반복문을 어떻게 이용해야할까?

 for (int j = i; j < s.length(); j += i) {
 }

이런식으로 이용하면 되지 않을까?

이게 뭐냐면 다음칸으로 점프시켜주는 역할을 코드다.

즉, abcd가 있다면

b c d

c_

d

이런식으로 점프가 된다.

d같은 경우는 뒤에 더이상 아무것도 없기 때문에 _가 없다.

근데 이렇게 하면 끝난걸까?

위 c를 보면 뒤에 _가 보인다. _에 뭔가를 넣어야할 것만 같다.

생각을 해보자.

c의 다음값인 d를 넣어야하는데 어떤식으로 넣어야 할까?

   for (int k = j; k < j + i && k < s.length(); k++) {
  }

바로 i+j가 핵심인데 이 말뜻은 j값에서 step(i)값을 추가해서 넣어줘야한다.

즉, c의 값은 2단계 이기 때문에 j값은 뭔지는 모르겠지만 2를 넣어주면 된다.

그러면 c는 2+x라는 식이 완성된다.

보면 c는 인덱스가 3이라는걸 알 수 있다.

그러면 x의 값은 1이 되는 걸까?

확실한건 아닌건 알고 있는데 이거는 전쳬코드를 봐야할것 같다.

그리고 나서 적절히 비교해가며 합치는 작업을 가지면 된다.

 

[전체 코드]

    public int solution(String s) {
        int ans = s.length();
        for (int step = 1; step < s.length(); step++) {
            String prev = s.substring(0, step);
            String compression = "";
            int cnt = 1;
            for (int i = step; i < s.length(); i += step) {
                String sub = "";
                for (int k = i; k < i + step && k < s.length(); k++) {
                    sub += s.charAt(k);
                }
                if (prev.equals(sub)) {
                    cnt++;
                } else {
                    compression += (cnt == 1) ? prev : cnt + prev;
                    cnt = 1;
                    prev = sub;
                }
            }
            compression += (cnt == 1) ? prev : cnt + prev;
            ans = Math.min(ans,compression.length());
        }
        return ans;
    }

이게 전체 코드인데

아까 보여줬던

새로운 문자열?을 만드는 코드를 파이썬에서는 어떻게 하는지 확인해 보자.

코드를 보면

s[j:j+step]

라는 걸 알 수 있다.

s는 문자열이다.

즉, j에서 j+step까지 한다는 이야기인데 자바에서도 될까? (자바에서는 불가능하지만 이코드가 자바에서 가능한다면 얼마나 줄어드는지 확인해보자)

private int solution(String s) {
        int ans = s.length();
        for (int step = 1; step < s.length(); step++) {
            String prev = s.substring(0, step);
            String compression = "";
            int cnt = 1;
            for (int i = step; i < s.length(); i += step) {
                String sub = s.substring(i,i+step);
                if (prev.equals(sub)) {
                    cnt++;
                } else {
                    compression += (cnt == 1) ? prev : cnt + prev;
                    cnt = 1;
                    prev = sub;
                }
            }
            compression += (cnt == 1) ? prev : cnt + prev;
            ans = Math.min(ans,compression.length());
        }
        return ans;
}

 아쉽게도 자바에서는 이 코드는 불가능한 코드이지만 파이썬으로는 이런식으로 이용이 가능하다.

더 줄이는 방법은 있지만, 딱히 필요는 없을 것 같다.

중요한건 이 코드는 되지 않는 코드인게 분명하다.

 

반응형

댓글

Designed by JB FACTORY