문제설명
주어진 문자열을 1개 이상 단위로 잘라 압축한 뒤 가장 짧은 것의 길이를 return하는 문제이다.
자세한 내용은 링크를 참고하시길 바란다...문제가 너무 길다
https://programmers.co.kr/learn/courses/30/lessons/60057
생각 생각
중첩 반복문을 사용해서 바깥쪽 반복문은 문자열을 자를 단위를 제어해주고, 안쪽 반복문은 문자열을 순회하면 될 것 같았다. 또, 안쪽에서는 조건문으로 앞,뒤 문자열을 비교하고, 동일한 문자열이라면 count를 증가시키는 방향으로 가기로 했다.
사실 이렇게 글로 코드를 어떻게 구현하겠다....하는건 시간 낭비인듯 하다... 코드로 넘어가자!
코드
class Solution {
public int solution(String s)
{
int answer = s.length(); // 문자열 s의 길이로 초기화.
// 1. 바깥쪽 반복문
// split : 문자열 나누는 길이.
// 문자열(s)의 반 까지만 반복문 진행. -> split이 s.length()/2 이상이 되면 어처피 비교할 대상이 없기 떄문.
for (int split = 1; split <= s.length() / 2; split++)
{
int count = 1;
StringBuilder resultStr = new StringBuilder();
// 2. 안쪽 반복문
for (int i = 0; i < s.length(); i += split)
{
int end = Math.min(i + split, s.length()); // end : substring에 들어갈 end Index
String substring; // 비교 할 앞 문자열
String eq = null; // 비교 할 뒤 문자열
//주어진 문자열 자르기(앞)
substring = s.substring(i, end);
if (end + split <= s.length())
{ // 주어진 문자열 자르기(뒤)
eq = s.substring(end, end + split);
}
// 3. 앞, 뒤 문자열 비교
if (substring.equals(eq))
{
count++; // 압축 성공했을 때 카운트 증가
}
else // 4. 압축이 한번이라도 성공했는지??
{
// 압축 한번도 못함
if ((count == 1))
{
resultStr.append(substring);
}
else
{ // 압축 한번이라도 성공 시
resultStr.append(count).append(substring);
count = 1; // 다시 count 초기화
}
}
}
// 5. answer(기존 문자열의 길이)보다 작으면 해당 값으로 대입.
if (answer > resultStr.length())
{
answer = resultStr.length();
}
}
return answer;
}
}풀이
1. 바깥쪽 반복문
바깥쪽 반복문은 문자열을 몇 개 단위로 자를지 정해주는 반복문이다. 'split'이 그 역할을 한다. s.length()/2로 한 이유는 주어진 문자열(s)를 몇 개 씩 잘라서 앞 문자열과 뒷 문자열끼리 비교하는데, 문자열 길이의 반 이상으로 자른다면 뒤쪽 문자열은 나머지 문자열이 되어서 압축할 수가 없게 되버린다. 예를들면 문자열의 길이가 11이라면, 반 이상인 6번까지 잘랐을 때 나머지 5개의 문자열이 남게 되버린다. 그렇기 때문에 문자열의 반까지 반복문을 돌게 했다.
2. 안쪽 반복문
안쪽은 위에서 설정된 split을 활용하여 문자열을 자르고 split을 기준으로 앞 문자열(substring)과 뒤 문자열(eq)로 나눈다. 이 때 주어진 문자열의 길이보다 넘는 인덱스를 참조하지 않도록 분기를 통해 제어해주었다.
3. 문자열 비교
앞 문자열과 뒤 문자열을 비교해서 동일하다면 압축 할 수있다는 의미이기 때문에 count를 증가시켜준다. 하지만 동일하지 않다면 더이상 동일한 문자열이 없다는 의미이므로 압축 이력이 있는지 count로 판단하여 다시 분기한다.
4. 압축이 한번이라도 성공했는지?
count==1 이라면 압축이 한번도 안되었다는 의미이므로 앞 문자열을 바로 넣어준다.
count!=1 이라면 압축이 한번이라도 되었다는 의미이므로 count를 먼저 넣어준 후, 문자열을 넣어준다. 그리고 count는 다시 1로 초기화 시켜준다.
5. 최소 문자열 길이 찾기
안쪽 반복문을 끝낸 후에 만들어진 문자열의 길이를 처음에 넣어놨던 주어진 문자열(s)의 길이(answer)와 비교한다. 만들어진 문자열의 길이가 더 작다면 answer에 대입해준다. 이를 바깥쪽 반복문이 돌면서 가장 작은 문자열의 길이를 넣어주게 된다.
REVIEW
역시 카카오는 문제를 읽고 해석하는데 시간이 오래걸리는 것 같다. 책좀 많이 읽을껄....
또, 무분별하게 쓸데없이 변수들을 생성하고 네이밍을 대충 짓는 짓은 그만하는게 좋을 것같다. 어떤 행동을 하더라도 작은 행동이라도 신중하게 생각하고 행동해보자.
