[2020 KAKAO BLIND RECRUITMENT][문자열 처리] 문자열 압축 - Java

문제 바로가기

코딩테스트 연습 - 문자열 압축

문자열을 다루는 문제입니다.

 

문자열을 몇 개 단위로 자를지 모두 봐줘야 하고, 문자열의 길이는 최대 1000이기 때문에 2중 for문으로 쉽게 풀 수 있습니다.

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

        for(int subLen=1;subLen<=s.length()/2; subLen++) {
            String newStr = "";
            String standard = s.substring(0, subLen);
            int cnt = 1;

            for(int i=subLen;i<s.length();i+=subLen) {
                if(i+subLen > s.length()) {
                    newStr+=s.substring(i);
                    break;
                }
                String comp = s.substring(i, i+subLen);

                if(standard.equals(comp)) cnt+=1;
                else {
                    if(cnt>1) newStr+=Integer.toString(cnt)+standard;                    
                    else newStr+=standard;

                    standard = comp;
                    cnt = 1;
                }
            }
            if(cnt>1) newStr+=Integer.toString(cnt)+standard;                    
            else newStr+=standard;

            answer = answer < newStr.length() ? answer : newStr.length();
        }
        return answer;
    }
}

subLen: 자른 문자열의 길이 (1개부터 s.length()/2개 만큼)

newStr: 압축한 문자열

standard: 비교의 기준이 될 문자열

cnt: 반복된 횟수

comp: 비교할 문자열

 

우선 subLen이 전체 문자열의 길이의 반보다 크다면 반복될 수 없으므로 subLen은 문자열의 반까지만 봐주면 됩니다.

 

standard를 먼저 구해주고 그 다음부터 comp를 구해서 standard와 comp를 비교하면서 cnt를 구해줍니다.

 

i+subLen > s.length()라면 마지막까지 체크를 한 것이므로 고대로 넣어주면 됩니다.

 

standard와 comp가 다르다면 cnt가 2 이상일 때 newStr에 숫자와 함께 반복된 문자열을 추가해주고, standard를 comp로 업데이트 시켜줍니다.

 

반복문이 다 돌았을 때 남은 것들을 newStr에 넣어주면 끝!

 

문자열을 여러 개 단위로 잘랐을 때, 길이의 최소값을 구해야 하므로

answer = answer < newStr.length() ? answer : newStr.length(); 로 answer를 구하면 끝입니다.

 

감사합니다

 

 

 

---

카카오 공채 뜬 김에 다시 풀어보았슴다... 이번엔 스택을 이용해서 풀어보았습니다..

저번에 풀었던 방법과 아이디어는 같습니다. 문자열의 길이가 1~length/2까지 잘라서 일일이 비교해주는거져.

다만 잘라서 스택에 넣어줌으로써 비교를 해줬습니다!!

스택의 top 에 있는 친구랑 비교하면서 같으면 넣고 다르면 빼는거져.

아이디어는 참 좋은데 맨마지막 문자열 자른 친구는 길이가 지맘대로기 때문에 이거 처리한다고 쪼까 걸렸슴니다.

 

public int solution(String s) {
		int answer = 1000;
		if(s.length() == 1) return 1;
		
		for (int i = 1; i <= s.length() / 2; i++) {
			StringBuilder compression = new StringBuilder();
			Stack<String> stack = new Stack<>();
			
			for(int j =0; j < s.length(); j+=i) {
				String sub;
				
				if(j + i > s.length()) 				// 마지막 부분 문자열
					sub = s.substring(j);
				else 
					sub = s.substring(j, j + i);
				
				if(stack.isEmpty()) {
					stack.push(sub);
					continue;
				}
				
				if(stack.peek().equals(sub)) {
					stack.push(sub);
				}else {
					int compLen = stack.size();
					compression.append(compLen > 1 ? compLen+stack.peek() : stack.peek());
					stack.clear();
					stack.push(sub);
				}
			}
			int compLen = stack.size();
			compression.append(compLen > 1 ? compLen+stack.pop() : stack.pop());
		
			answer = Math.min(answer, compression.length());
		}

		return answer;
	}