[Lv.2] 문자열 압축 : Java

프로그래머스

 

 

 

이해하기

처음 생각했던 건 문자열의 길이의 약수들로 쪼개어보는 것이었다.

예를 들어 "aabbaccc" 의 길이는 8이니 스스로를 제외한 약수인 1, 2, 4로 문자열을 쪼개보는 것이다.

 

하지만 역시나 fail...

왜일까 생각해봤는데 약수로 접근했던 방법이 틀렸던 것 같다.

굳이 약수가 아니더라도 주어진 문자열의 절반까지만 for문을 돌리면 된다.

(절반으로 잡은 이유 : 절반을 넘게 되면 2번 이상 반복 불가)

 

 

문제풀이

class Solution {
    public int solution(String s) {
        int answer = s.length();
        int count = 1;

        for (int i = 1; i <= s.length() / 2; i++) {
            StringBuilder sb = new StringBuilder();
            String base = s.substring(0, i);
            for (int j = i; j <= s.length(); j += i) {
                int endIdx = Math.min(j + i, s.length());
                String compare = s.substring(j, endIdx);
                if (base.equals(compare)) {
                    count++;
                } else {
                    if (count >= 2) {
                        sb.append(count);
                    }
                    sb.append(base);
                    base = compare;
                    count = 1;
                }
            }
            sb.append(base);
            answer = Math.min(answer, sb.length());
        }
        return answer;
    }
}

 

int answer = s.length();
int count = 1;

 

answer는 후에 압축 결과 길이와 비교할 용도로 사용할 것이니 최대 길이인 s.length()로 잡는다.

count를 0이 아닌 1로 잡은 이유는 첫 번째 for문에서 설명하겠다.

 

for (int i = 1; i <= s.length() / 2; i++) {
	StringBuilder sb = new StringBuilder();
	String base = s.substring(0, i);

 

습관적으로 String을 매번 사용하는데, 다른 분의 정리글을 보고 StringBuilder를 사용해보았다.

문자열의 연산이 자주 이루어지는 경우, String보다 StringBuilder의 부하가 적기 때문이라고 한다.

여기에서 비교 기준으로 사용될 base를 s.substring()으로 가져온다.

이 때 문자열 count가 한 번 이루어진다고 생각하여 위에서 count를 1로 잡은 것이다.

 

for (int j = i; j <= s.length(); j += i) {
	int endIdx = Math.min(j + i, s.length());
	String compare = s.substring(j, endIdx);
	if (base.equals(compare)) {
		count++;
	} else {
		if (count >= 2) {
			sb.append(count);
		}
		sb.append(base);
		base = compare;
		count = 1;
		}
	}

 

j는 i부터 시작해서 for문을 돌고난 후, i만큼 늘어난다.

예를 들어, 위에서 i가 1이었다면 1씩 늘어난다. (문자 1개씩 압축하는 경우)

또, 위에서 i가 4였다면 4씩 늘어난다. (문자 4개씩 압축하는 경우)

 

endIdx를 j + i (j부터 시작해서 j + i - 1 까지 떼어오기 위함) 만큼 잡는데, 이 때 문자열의 길이를 넘어갈 수 있으므로 Math.min()을 사용한다.

compare에 비교할 다음 문자열을 substring()으로 가져온다.

 

만약 base와 compare가 같다면 count를 1 증가시키고 다시 for문 첫 줄로 돌아간다.

만약 둘이 같지 않다면 else문으로 가게 되는데, 이 때 count가 2 이상이면 "2a"와 같이 적어야 하므로 sb.append(count)로 count 수를 sb에 추가한다.

count가 1이라면 적을 필요 없으니 이에 대한 처리는 생략한다.

sb.append(base)로 "2a" 와 같이 문자를 적어준다.

기준이 되는 문자열인 base를 다음 문자열인 compare로 바꾸고 count를 1로 초기화한 후 for문의 첫 줄로 돌아간다.

 

sb.append(base);
answer = Math.min(answer, sb.length());

 

sb.append(base)를 추가한 이유는 혹시라도 빠지게 될 마지막 문자열을 추가해주기 위함이다.

answer = Math.min(answer, sb.length())를 통해 압축한 문자열의 길이와 answer를 비교해 가장 작은 값을 저장한다.

 

 

 

처음부터 약수를 사용해야지!라는 생각에 꽂혀버려서 계속 Fail이 났다ㅠ

안 되면 다른 방법으로 시도해보아야 하는데, 한 가지에 꽂히면 새로운 생각을 하기가 어려운 것 같다.

다른 분들의 풀이를 참고해서 풀이하고 정리한 것이니 내 식대로 다시 한 번 풀어보아야지!

 

 

---

 

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