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

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 문자열 압축

 

난이도: LEVEL2

알고리즘 유형: 구현

풀이 설명 

나는 스택을 활용해서 문제를 풀었다. 

Element class 

static class Element{
    int value;
    String str;
    public String toString(){
        return value + " " + str;
    }
}

 

누적 숫자를 나타내는 value 문자열을 기록하는 str 

성능을 위해 고려한 부분 

Stack과 StringBuilder는 static으로 만들고 매번 검사에서 clear or setLength(0)을 하는 방식으로 초기화하여
매번 검사마다 객체 생성에 대한 비용을 없앴다. 

 static Stack<Element> stack = new Stack<>();
 static StringBuilder sb = new StringBuilder();

 

또한 문자열 s에 대한 각 index 별 문자가 매번 for문에서 필요하니 

미리 for문을 한번 돌고 배열(array)에 저장했다.
문자열 더하기를 쉽게 하기 위해서 charAt()을 사용해서 문자를 뽑고 문자열로 변환하여 저장  

static String [] array;
array = new String[length];
for(int i = 0; i < length; i++){
    array[i] = Character.toString(s.charAt(i));
}

 

핵심 로직 설명

나는 size를 정해놓고 size 마다 검사를 진행하였다.

size가 문자열 s 절반을 넘어서면 pair를 못 찾으니 s 길이의 절반까지만 검사를 하였다.

대신 answer의 초기화는 처음 s의 길이로 하였다. (압축 실패 케이스)

pair를 못 찾는 경우 처음 문자열 길이 그대로 반환  

static int answer;
answer = s.length();
for(int i = 1; i <= length / 2; i++){
    check(i);
}

 

stack의 현재 peek 문자열이 이번에 검사할 size 보다 작으면 peek에 문자를 추가 / cnt 유지 

만약 size가 같으면 새로운 Element 객체를 만들어서 문자를 저장 / cnt 추가 

 

만약 cnt == 2 이고 peek() 문자열 길이가 이번에 검사할 사이즈와 같다면 

비교할 2개의 문자열이 만들어진 것이다. 그래서 검사 진행 

 

검사는 먼저 stack에서 Element를 하나 빼고 

peek().str과 방금 pop한 str을 비교한다.

같으면 처음 문자열 누적을 하는 경우라면 2개니까 2를 추가하고 

이미 누적을 했다면 + 1을 해준다. 

 

만약 문자를 비교했는데 다르다면 다음 검사에 필요하니 다시 stack에 넣어준다.

 

2가지 케이스 모두 이번 요소를 검사한 것이니 cnt를 줄여준다. 

해당 과정을 문자열 s 전체를 검사할 때까지 반복해 준다. 

public static void check (int size){
    Element start = new Element();
    start.str = array[0];
    stack.push(start);
    int cnt = 1;
    for(int i = 1; i < length; i++){
        if(stack.peek().str.length() < size){
            stack.peek().str += array[i];
        }
        else{
            Element temp = new Element();
            temp.str = array[i];
            stack.push(temp);
            cnt++;
        }
        if(cnt == 2 && stack.peek().str.length() == size){
            Element temp = stack.pop();
            if(temp.str.equals(stack.peek().str)){
                if(stack.peek().value == 0){
                    stack.peek().value = 2;
                }
                else stack.peek().value++;
            }
            else{
                stack.push(temp);
            }
            cnt--;
        }
    }
    result();
}

 

check에서 누적한 문자열의 길이를 판단하는 result 메소드 

public static void result(){
    sb.setLength(0);
    while(!stack.isEmpty()){
        Element cur = stack.pop();
        if(cur.value > 0){
            sb.append(cur.value);
            sb.append(cur.str);
        }
        else sb.append(cur.str);
    }
    answer = Math.min(answer, sb.length());
    stack.clear();
}

전체 정답 코드 

import java.util.*;
class Solution {
    static class Element{
        int value;
        String str;
        public String toString(){
            return value + " " + str;
        }
    }
    static int answer;
    static int length;
    static Stack<Element> stack = new Stack<>();
    static StringBuilder sb = new StringBuilder();
    static String [] array;
    public int solution(String s) {
        answer = s.length();
        length = answer;
        array = new String[length];
        for(int i = 0; i < length; i++){
            array[i] = Character.toString(s.charAt(i));
        }
        for(int i = 1; i <= length / 2; i++){
            check(i);
        }
        return answer;
    }
    public static void check (int size){
        Element start = new Element();
        start.str = array[0];
        stack.push(start);
        int cnt = 1;
        for(int i = 1; i < length; i++){
            if(stack.peek().str.length() < size){
                stack.peek().str += array[i];
            }
            else{
                Element temp = new Element();
                temp.str = array[i];
                stack.push(temp);
                cnt++;
            }
            if(cnt == 2 && stack.peek().str.length() == size){
                Element temp = stack.pop();
                if(temp.str.equals(stack.peek().str)){
                    if(stack.peek().value == 0){
                        stack.peek().value = 2;
                    }
                    else stack.peek().value++;
                }
                else{
                    stack.push(temp);
                }
                cnt--;
            }
        }
        result();
    }
    public static void result(){
        sb.setLength(0);
        while(!stack.isEmpty()){
            Element cur = stack.pop();
            if(cur.value > 0){
                sb.append(cur.value);
                sb.append(cur.str);
            }
            else sb.append(cur.str);
        }
        answer = Math.min(answer, sb.length());
        stack.clear();
    }
}

 

0.04 ms (최소)  ~ 151.44 (최대) ms 

가장 오래 걸린 케이스가 0.15초 이니 무난하게 통과했다.