<1.11> 문자열 압축

문제
: 대문자로 이루어진 문자열을 입력받아, 같은문자가 연속으로 반복되는 경우 그 문자 바로 오른쪽에 반복 횟수를 표기하고, 반복되지 않는 문자는 그대로 문자를 유지하는 방식으로 문자열을 압축하라

문제를 읽고 요구사항을 바로 파악할 수 있었다. 요구사항은 문제에 주어진 그대로 "문자열을 순차탐색 하면서 연속된 부분만을 압축"하기 였다.

결국 해결의 핵심은 "연속된 부분을 압축"을 어떤식으로 구현하는가 였고,
직관적으로 문자열이 반복되는 부분의 끝와 새로운 문자가 시작되는 "그 경계 부분"을 가장 잘 인식할 수 있는것이 "스택" 이라는 생각이 들었다.

따라서 스택을 사용하여 아래와 같은 해결 로직을 구상하였다.

[스택을 사용한 문자열 압축]

• 주어진 문자열을 문자 단위로 순차탐색 하면서
  • case1. 스택이 비어있는 경우라면 일단 push
    • 이는 순차탐색을 처음 시작하는 경우에 해당
  • case2. 스택에 어떤 문자가 1개 이상 쌓여있는 경우라면
    • 쌓여있는 문자와 push할 문자가 같다면 push (연속된 문자 이니깐)
    • 문자가 같지 않다면 , 스택에 쌓인 연속된 문자를 모두 꺼내 그 개수가 2이상이면 "문자+개수"형태로 압축시키고 OR 개수가1개면 그 문자그대로사용 -> 이후 새로운 문자를 push

위와 같은 로직을 사용할 경우,
순차 탐색되는 모든 문자는 일단 스택에 쌓이고,
새로운 문자가 시작되는 경계를 만날 때 마다 쌓인 문자가 비워지면서 압축이 된다.

위와 같은 로직을 그대로 아래와 같은 코드로 구현하였다.
이때 새로운 문자가 시작되는 경계를 만나 스택을 비우면서 문자를 압축하는 로직을, 별도의 stackClear()라는 메서드로 묶었다.

import java.util.Scanner;
import java.util.Stack;

public class Main {

    //이 stackClear()를 호출한다는건 -> push하려는 문자와 , 지금 스택에 쌓인 문자가 달라서 스택을 비워야 하기 때문.
    // 따라서 스택에 stackClear()를 호출하는 시점에는, 스택에 연속된 문자가 쌓인 시점일 수밖에 없음.
    public static String stackClear(Stack<Character> stack){

        String result = "";
        int size = stack.size();
        Character c = stack.pop();

        //스택에 있는 문자가 하나면 -> 그냥 이어 붙이고
        if(size==1){
            result += c;
        } else{
            //스택에 있는 문자가 2개 이상이면 -> 연속된 숫자를 뒤에 이어 붙여야 함
            result += (c + String.valueOf(size));
        }

        stack.clear();
        return result;
    }

    public static String solution(String str){
        char[] charArr = str.toCharArray();
        Stack<Character> stack = new Stack<>();
        String result = "";

        for(int i=0; i<str.length(); i++){

            // 스택이 비어있으면 일단 push
            if(stack.isEmpty()){
                stack.push(charArr[i]);
            } else{
                //스택이 비어있지 않으면 , 스택에 있는 문자와 , 넣으려는 문자를 비교하여 -> 일치하면 push / 일치하지 않으면 stackClear()
                Character peekChar = stack.peek();
                if(charArr[i] == peekChar){
                    stack.push(charArr[i]);
                } else{
                   result += stackClear(stack);
                   stack.push(charArr[i]);
                }

            }

            // 방금 처리한 문자가 마지막 문자라면 -> 어쨌거나 stackClear() 하여 최종 결과 문자열에 반영
            if(i == str.length()-1){
                result += stackClear(stack);
            }
        }

        return result;
    }
    public static void main(String[] args){
        //0. Scanner 준비
        Scanner sc = new Scanner(System.in);

        //1. 문자열 입력
        String str = sc.next();

        //2. 문자열을 인자로 넘기면서 solution()을 호출하여 , 그 결과를 반환
        String result = solution(str);

        //3. 결과 출력
        System.out.println(result);
    }
}

[이 문제를 통해 알게된 점 정리]

• stack.push() : 그냥 push
• stack.pop() : 스택의 마지막 element를 꺼내면서 반환
• stack.peek() : 스택의 마지막 element를 꺼내진 않고, 반환
• stack.isEmpty() : 스택에 element 존재 여부 확인
• stack.clear() : 스택의 모든 element를 꺼내 , empty하게 만듦
• stack.size() : 현재 스택 안에 push 된 element 개수 반환