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

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

프로그래머스

---

[1회차] 11월 8일, 문제 추천받음

문제 접근 방법 (사용 자료구조, 알고리즘)

 

일단 스토리라인을 적어보자면 다음과 같다, 사실 반복문으로 풀어야 하는 문제인거 알고 있었는데(6개월 전에 파이썬으로 품) 도전해보고 싶었음... 도전 정신 쯤으로 봐주길...

 

[조건과 출력] 문자열은 제일 앞에서부터 잘라야… ⇒ 가장 짧은 길이 출력하기

주어지는 문자열을 자를 수 있는 경우들 (1 ~ N)개 이지만 반복되려면 2개는 나와야하므로 (1 ~ N/2)개 까지만 탐색하면 됨.

앞에서부터 i개(1~N/2)씩 문자열을 잘라보면서 일치하지 않는 경우는 다른 N 길이의 필터를 만들어주고 일치하면 카운트해주기

 

dfs? 해보자

 

로직
dfs(int start, int length, String search, String origin, int r)
start : 탐색 시작 인덱스
length : 탐색할 문자열의 길이
search : 현재 탐색하는 문자열
origin : 전체 문자열
r : 문자열이 반복한 갯수

(0) [베이스 조건] 탐색시작 index > 문자열 길이 - 1
      가장 마지막 탐색 문자열이 나머지 문자열에 들어있는지 확인 & 그리고 남은 문자열의 갯수 더해주기
[처리문] : 재귀조건
(1) 현재 문자열의 index(start) 에서 index + length 만큼의 문자열 구하기 → cur
(2) 만약 현재 문자열의 인덱스가 0 이라면, 탐색 문자열이 없으므로 ➡ dfs(start + length, length, cur, origin, 1) 수행
(1) cur 과 search 가 같다면 반복한다는 의미 ➡ dfs(start + length, length, search, origin, r + 1) 수행 
(2) cur 과 search 가 같지 않다면 새로운 탐색 문자열이 생김
➡ 문자열이 바뀌기 이전까지 반복된 횟수(r)의 자릿수를 계산해서 (Math.log10(r) + 1) 문자열의 갯수에 더해줌 
➡ dfs(start + length, length, cur, origin, 1)

 

 

메모리 & 시간

테스트 1 〉	통과 (11.31ms, 72.4MB)
테스트 2 〉	통과 (23.16ms, 72.2MB)
테스트 3 〉	통과 (14.65ms, 78.4MB)
테스트 4 〉	통과 (12.35ms, 85.6MB)
테스트 5 〉	통과 (0.02ms, 72.8MB)
테스트 6 〉	통과 (13.42ms, 70.7MB)
테스트 7 〉	통과 (19.61ms, 86.8MB)
테스트 8 〉	통과 (23.45ms, 81.8MB)
테스트 9 〉	통과 (25.40ms, 84.1MB)
테스트 10 〉	통과 (97.57ms, 122MB)
테스트 11 〉	통과 (14.49ms, 83.4MB)
테스트 12 〉	통과 (19.75ms, 79.9MB)
테스트 13 〉	통과 (16.91ms, 83.2MB)
테스트 14 〉	통과 (28.87ms, 87.3MB)
테스트 15 〉	통과 (15.52ms, 75.2MB)
테스트 16 〉	통과 (12.54ms, 70.9MB)
테스트 17 〉	통과 (41.57ms, 96.2MB)
테스트 18 〉	통과 (43.03ms, 104MB)
테스트 19 〉	통과 (48.69ms, 99.5MB)
테스트 20 〉	통과 (95.47ms, 139MB)
테스트 21 〉	통과 (67.87ms, 129MB)
테스트 22 〉	통과 (102.03ms, 140MB)
테스트 23 〉	통과 (68.63ms, 128MB)
테스트 24 〉	통과 (63.86ms, 112MB)
테스트 25 〉	통과 (69.39ms, 123MB)
테스트 26 〉	통과 (70.92ms, 134MB)
테스트 27 〉	통과 (72.37ms, 131MB)
테스트 28 〉	통과 (11.26ms, 90.3MB)

확실히 반복문보다 시간이 압도적으로 많이 나오기는 한다. 

 

 

 

코드

class Solution {
    static int size, strSize;
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        size = s.length();
        
        if(size == 1) return 1;
        
        for (int i = 1; i <= size / 2; i++) {
        	strSize = 0;
        	dfs(0, i, "", s, 0);
        	answer = answer > strSize? strSize : answer;
		}
        return answer;
    }
    
    private static void dfs(int start, int length, String search, String origin, int r){
		if(start > size - 1 || start + length > size) {
			if(r > 1) strSize += (length + (int)( Math.log10(r) + 1));
			else strSize += length;
			
			strSize += (size - start);
			return;
		}
		
		String cur = "";
		for (int i = start; i < start + length; i++) {
			cur += origin.charAt(i);
		}
		
		if(start == 0) {
			dfs(start + length, length, cur, origin, 1);
		} else if(cur.equals(search)) {
			dfs(start + length, length, search, origin, r + 1);
		} else if(!cur.equals(search)) {
			if(r > 1) strSize += (length + (int)( Math.log10(r) + 1));
			else strSize += length;
			dfs(start + length, length, cur, origin, 1);
		}
	}
}

 

 

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 접근	코드 구현
10분	20분	40분

 

 

 

코드 리뷰 받은 것

같이 문제 푼 사람들 중 직접 추가하는 방식 말고 자릿수를 계산해서 추가한 사람이 처음이라고 하셨는데 저 대로 for문으로 다시 구현해서 추후에 올리도록 하겠음!