이번에 소개할 문제는 문자열 압축이라는 알고리즘 문제이다.
해당 문제는 데이터를 처리할 때 최소한의 메모리를 사용하여 문자열을 저장하고 싶은 게 핵심인 문제인 거 같다.
예를 들어보면 "가나다라마바사아"라는 문자열이 존재한다고 가정해보자.
이때 해당 문자열을 그대로 저장하게 되면 8글자를 Byte로 저장하게 된다.
위와 같이 중복된 글자가 없으면 그대로 저장하는 것이 데이터의 정확도상 당연한 것이라 생각한다.
하지만 "가가가나나나나나나다다다다다라라라마마바"라는 문자열이 있다고 생각해보자.
위와 같은 문자열이 있을 때 해당 문자열을 그대로 저장하는 것은 20개의 글자를 Byte로 저장하는 것이다.
이럴 때 동일한 문자가 연달아 존재할 때 몇 개인지를 앞에 명시하여 보다 짧은 문자열로 저장하는 것이 훨씬 적은 데이터를 가지고 저장을 할 수 있다.
또한 문자열을 줄일 때 1 단어 단위로 줄이면 "3가6나5다3라2마바"와 같은 형태로 저장되는 것이고,
2 단위로 줄이면 "가가가나2나나나다2다다라라라마마바"라는 문자열로 저장되는 식으로 몇 개 단위로 잘라 저장하느냐에 따라 저장되는 데이터 양에 차이를 주게 된다.
다시 문제로 돌아가서 해당 문제는 데이터를 최소한 짧은 문자열로 저장하고 싶은데 n단위로 잘라 저장했을 때 가장 적을 경우 가장 짧은 문자열일 경우 해당 문자열의 length를 구하여라로 생각하면 될 거 같다.
우선 default를 지정하도록 하자.
int answer = s.length();
해당 default로 지정한 경우는 어떤 방법으로 문자열을 압축한다 하더라도 기본 문자열보다 길어질 수 없기 때문에 기본 문자열의 length를 default로 지정하였다.
이후 먼저 중요하게 생각한 것은 문자열을 자를 건데 몇 개 단위로 자를지에 관해 먼저 생각하기로 하였다.
for(int i = 1; i< s.length() /2 +1; i++) {
}
문자열을 자를 거지만 절반을 넘어갈 경우 어차피 default와 길이는 같을 테니 적절하게 max를 지정해 주었다.
이후 잘라 만들어진 문자열과 이전 값을 비교하기 위한 변수와 몇 번째 압축인지를 알기 위한 변수를 선언해 주었다.
// i 는 자르는 갯수
for(int i = 1; i< s.length() /2 +1; i++) {
StringBuffer sb = new StringBuffer();
//이전값
String bef = "";
// 압축 count default 1
int zipNum = 1;
}
이후부터는 subString으로 문자열을 자르기 위해 반복문을 돌려 문자열을 자르는 startPoint와 endPoint를 지정해 주도록 하자.
for (int j = 0; j < s.length(); j++) {
//마지막 index
int endNum = i+j > s.length() ? s.length() : i+j;
//현재
String sub = s.substring(j, endNum);
}
위에서 나온 sub의 값은 현재 잘려 나온 문자열의 값이다.
현재 잘려나온 값을 알았으니 이제 해당 값이 압축이 가능한 문자열인지 check를 해볼 차례이다.
for(int i = 1; i< s.length() /2 +1; i++) {
StringBuffer sb = new StringBuffer();
String bef = "";
int zipNum = 1;
for (int j = 0; j < s.length(); j++) {
//마지막 index
int endNum = i+j > s.length() ? s.length() : i+j;
//현재
String sub = s.substring(j, endNum);
if (!sub.equals(bef)) {
bef = sub;
zipNum = 1;
}
else {
zipNum++;
}
}
}
bef = 이전 값.
sub = 현재 값.
위 두 값을 비교하여 같을 경우 압축 가능한 문자열이니 zipNum을 올려주며 끝나고,
문자열이 같지 않을 경우 압축할 수 없는 값이니 다음 단계를 진행해 주었다.
if (!sub.equals(bef)) {
if(zipNum > 1) {
sb.append(zipNum);
}
if (!bef.equals("")) {
if (endNum != s.length()) {
sb.append(bef);
}
else {
sb.append(bef).append(sub);
}
}
bef = sub;
zipNum = 1;
}
else {
zipNum++;
if (endNum == s.length()) {
sb.append(zipNum).append(bef);
}
}
자른 문자열이 이전과 이후가 같을 확률은 다를 경우보다 높아 if문 앞 조건에서 처리를 할 수 있도록 하였다.
zipNum이 1보다 클 경우 해당 문자열은 이미 앞에서 문자열 압축이 이뤄진 것이니 압축이 된 문자열 숫자를 붙여주고,
이전 문자를 붙여줌과 동시에 현재 잘린 문자열이 기존 문자열의 마지막 단계가 아닐 경우 bef에 값을 저장하여 이후 들어올 잘린 문자열이 현재 값과 비교를 할 수 있게 조절해준다.
문자열이 서로 같을 경우 zipNum을 1올려줌과 동시에 현재 문자열이 마지막 문자열인지 체크하여 값을 추가해주도록 하여 값이 빠지는 경우가 생기지 않게 해 주었다.
이대로 끝났으면 좋겠지만 아직 2가지를 더 처리를 해 주어야 한다.
우선 현재 문자열을 자를 때 j의 값을 사용하게 되는데 해당 값은 무조건 1씩 오르기 때문에 2개 이상의 단어를 자르게 될 시 값이 중복되어 나오는 경우가 생기게 된다.
설명을 하자면 본인이 원하는 경우는 1, 3, 5, 7, 9와 같이 2단계씩 건너뛰려 하는데 이 코드를 지금 상태로 사용하게 될 시 1, 2, 3, 4, 5, 6, 7, 8, 9와 같이 1단계씩 건너 2 단어씩 잘라 앞 문자열의 뒷 단어와 뒷 문자열의 앞 단어가 곂치는 현상이 발생하는 것이다.
이를 해결하기 위해선
for(int i = 1; i< s.length() /2 +1; i++) {
StringBuffer sb = new StringBuffer();
String bef = "";
int zipNum = 1;
for (int j = 0; j < s.length(); j++) {
int endNum = i+j > s.length() ? s.length() : i+j;
if (!sub.equals(bef)) {
if(zipNum > 1) {
sb.append(zipNum);
}
if (!bef.equals("")) {
if (endNum != s.length()) {
sb.append(bef);
}
else {
sb.append(bef).append(sub);
}
}
bef = sub;
zipNum = 1;
}
else {
zipNum++;
if (endNum == s.length()) {
sb.append(zipNum).append(bef);
}
}
//단계를 조절하기 위해 값을 현재 end값 -1로 명시해준다.
j = endNum - 1;
}
}
j = 문자열 자르는 단계 (index)
j를 마지막 잘랐던 index번호로 변경해주면 반복문이 작동하며 j++로 인해 의도했던 번호보다 1이 많아지게 되어 -1을 해주면 정상적으로 작동하게 된다.
subString의 용도상 startIndex부터 ~ endIndex전까지 잘라주게 되는데 위와 같이 해주면 이전 문자열의 index 다음 index부터 문자열을 잘라주게 되어 값의 중복 없이 정상적으로 작동하게 된다.
마지막으로
answer = answer > sb.toString().length() ? sb.toString().length() : answer;
잘랐던 문자열을 toString()으로 하나의 문자열로 뽑아 보았을 때 해당 문자열의 길이가 이전에 잘라서 합친 문자열보다 짧을 경우 해당 값을 정답으로 제출하기 위해 비교하며 저장한다.
제출 코드
class Solution {
public int solution(String s) {
int answer = s.length();
for(int i = 1; i< s.length() /2 +1; i++) {
StringBuffer sb = new StringBuffer();
String bef = "";
int zipNum = 1;
for (int j = 0; j < s.length(); j++) {
int endNum = i+j > s.length() ? s.length() : i+j;
String sub = s.substring(j, endNum);
if (!sub.equals(bef)) {
if(zipNum > 1) {
sb.append(zipNum);
}
if (!bef.equals("")) {
if (endNum != s.length()) {
sb.append(bef);
}
else {
sb.append(bef).append(sub);
}
}
bef = sub;
zipNum = 1;
}
else {
zipNum++;
if (endNum == s.length()) {
sb.append(zipNum).append(bef);
}
}
j = endNum - 1;
}
answer = answer > sb.toString().length() ? sb.toString().length() : answer;
}
return answer;
}
}
해당 문제를 풀면서 stream을 사용하며 풀거나 재귀 함수를 사용할 시 훨씬 코드가 줄어들게 되지만 아직 실력이 부족하기도 하고 외부 라이브러리를 사용하지 않고 직접 돌아가는 상황을 작성해보고 싶어 위와 같이 작성하게 되었다.
다음에 stream이나 재귀함수를 공부하며 Refactoring 해 보아야겠다.
