프로그래머스 레벨2 문자열 압축
알고리즘 풀이
1. 가능한 모든 문자열의 조합을 찾아야되는줄 알고 문자열 조합만들고, ArrayList.contains() 써서 중복 제거할려하고 여러가지 고생을 함
substring(s, t) 계산하고, substring(s, length())해서 s부터 시작하는 문자열 다시 만들고 replace(sub, "#")해서 # 개수 찾고 이런 수고를 함
-> 이렇게 하니까 "xababcdcdababcdcd" 테스트케이스가 x2ababcdcd로 되서 오답이 나왔던걸로 기억함. 다시 문제보고 잘못 계산했다는걸 깨닮음
-
for 한번만 돌아서 맨 앞에서부터 (0, i)로 만든 substring을 #으로 바꾸고 #이면서 i, i+1이 같은 걸 찾고, 아니면 break 이런식으로 하다보니까 ##asdbeqwe## 일때 마지막 ##를 못찾는 경우가 발생
-
##asdfsa## 이런걸 다 계산해줬는데도 케이스 몇개가 계속 실패남
-> 3ab에서 숫자각 생기는걸 항상 +1로 해줬는데 100ab일 경우를 생각못함 (Math.log10()) 으로 해결함.
import java.util.Collections;
import java.util.ArrayList;
import java.lang.Math;
class Solution {
public int solution(String s) {
int answer = 0;
ArrayList<Integer> ans = new ArrayList<>();
// 문자열 개수
for(int i = 1; i <= s.length(); i++)
{
int total = s.length();
int cnt = 0;
int st;
for(st = 0; st + 2 * i <= s.length(); st += i)
{
if(s.substring(st, st+i).equals(s.substring(st + i, st + 2*i)))
cnt++;
else
if(cnt > 0){
total = total - (i * cnt) + ((int)Math.log10(cnt+1) + 1);
cnt = 0;
}
}
if(cnt > 0)
total = total - (i * cnt) + ((int)Math.log10(cnt+1) + 1);
ans.add(total);
}
Collections.sort(ans);
if(ans.isEmpty())
answer = s.length();
else
answer = ans.get(0);
return answer;
}
}
Author And Source
이 문제에 관하여(프로그래머스 레벨2 문자열 압축), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cminmins/프로그래머스-레벨2-문자열-압축저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)