[JAVA-알고리즘 문제풀이] 문자열 압축

문제 - 문자열 압축

알파멧 대문자로 이루어진 문자열을 입력받아 같은 문자가 연속으로 반복되는 경우,

반복되는 문자 바로 오른쪽에 반복 횟수를 표기하는 방법으로 문자열을 압축하는 프로그램을 작성하시오.

단, 반복횟수가 1인 경우는 생략

 

[입력]

첫 줄에 문자열, 길이는 100을 넘지 않는다.

 

[출력]

첫 줄에 압축된 문자열을 출력

 

[입력 예제]

KKHSSSSSSSE

 

[출력 예제]

K2HS7E

 

 

 

나의 풀이

package com.algorithm._01_그리디_구현;

import java.util.Scanner;

public class LC11_문자열_압축 {
    static int N;
    static String str;

    public static void main(String[] args) {
        // write your code here
        LC11_문자열_압축 sample = new LC11_문자열_압축();
        sample.solution();
    }

    public void solution() {
        input();

        // 마지막에 빈문자열 넣기
        str = str + " ";

        StringBuilder result = new StringBuilder();
        String beforeTarget = String.valueOf(str.charAt(0));

        int cnt = 1;
        for (int i = 1; i < str.length(); i++) {
            String target = String.valueOf(str.charAt(i));

            if (target.equals(beforeTarget)) {
                cnt++;
            } else {
                result.append(beforeTarget);

                if (cnt > 1) {
                    result.append(cnt);
                }

                beforeTarget = target;
                cnt = 1;
            }

        }

        System.out.println(result);
    }

    private void input() {
        Scanner sc = new Scanner(System.in);
        str = sc.next();
    }
}

1) 입력받은 문자열 마지막에 빈 문자열을 추가한다.

문자열에서 마지막 문자까지 결과 문자열(변수 result)에 담기 위함이다.

 // 마지막에 빈문자열 넣기
 str = str + " ";

 

2) 같은 경우와 다른 경우의 분기 처리

if (target.equals(beforeTarget)) { // 같은 경우
    cnt++;
} else { // 다른 경우
    result.append(beforeTarget);

    if (cnt > 1) {
        result.append(cnt);
    }

    beforeTarget = target;
    cnt = 1;
}

▶ 같은 경우

cnt 를 +1 증가한다.

 

▶ 다른 경우

결과 스트링(result)에 문자열을 넣고, cnt 가 1 이상인 경우 cnt도 문자열에 넣는다.

beforeTarget은 현재 target 문자열로 대체하고, cnt 도 1로 다시 초기화한다.

 

 

 

해설 풀이

package com.algorithm._01_그리디_구현;

import java.util.Scanner;

public class LC11_문자열_압축 {
    static int N;
    static String str;

    public static void main(String[] args) {
        // write your code here
        LC11_문자열_압축 sample = new LC11_문자열_압축();
        sample.solution2();
    }

    public void solution2() {
        String answer = "";
        str = str + "";

        int cnt = 1; // 1로 초기화
        for (int i = 0; i < str.length() - 1; i++) {
            // 같으면
            if (str.charAt(i) == str.charAt(i + 1)) {
                cnt++;
            } else { // 다르면
                answer += str.charAt(i);

                if (cnt > 1) {
                    answer += cnt;
                }

                cnt = 1;
            }
        }

        System.out.println(answer);
    }

    private void input() {
        Scanner sc = new Scanner(System.in);
        str = sc.next();
    }
}

대체적으로 내가 풀이한 방식과 비슷했다.

 

1) 같은 경우와 다른 경우의 분기 처리

for (int i = 0; i < str.length() - 1; i++) {
    // 같으면
    if (str.charAt(i) == str.charAt(i + 1)) {
        cnt++;
    } else { // 다르면
        answer += str.charAt(i);

        if (cnt > 1) {
            answer += cnt;
        }

        cnt = 1;
    }
}

▶ 같은 경우

cnt 를 +1 증가한다.

 

▶ 다른 경우

결과 스트링(answer)에 문자열을 넣고, cnt가 1 이상인 경우 cnt를 넣고, cnt를 1로 초기화한다.

 

 

풀이 분석

중요한 로직은 비슷했는데, 나는 beforeTarget 변수를 사용해서 비교를 했고 해설 풀이에서는 i와 i + 1번째를 직접 비교하여 처리했다. 해설 풀이에서 위와 같은 방법을 선택한 이유는 다음과 같다.

 

0	1	2	3	5	6	7	8	9	9	10
K	K	H	S	S	S	S	S	S	S	E

 

반복문 for ( i = 0; i < str.length() - 1; i++)

i = 0	[초기화] cnt = 1 [체크] i번째 문자열 == i + 1번째 문자열 비교 1) 같을 경우 - cnt +1 증가
i = 1	[체크] i번째 문자열 == i + 1번째 문자열 비교 1) 다를 경우 - answer 에 문자열 누적 - cnt 가 1 이상일때 answer에 cnt 누적 - cnt를 1로 초기화
i = 2	위와 동일하게 계속해서 체크
...
i = 10	마지막 문자열(i번째는) i + 1 = 11번째 문자열과 체크되는데, 처음에 입력받은 문자열(str)의 마지막 문자열에 임의로 빈값(" ")을 넣었기 때문에 체크가 되고, 마지막 문자열은 제외해야하므로 for문의 범위가 str.length() -1 이 된다.