[프로그래머스 60057] 문자열 압축 (java)
나의 풀이
저는 하드 코딩했습니다. 문제의 해답 코드가 궁금하다면, 나의 풀이는 건너 뛰고 아래의 모범 답안을 확인 부탁드립니다.
내 자신이 이렇게 복잡하게 짤 수 있음에 놀라웠고, 그 와중에도 통과했다고 좋아하는 날 보면서 너무 슬펐다..
cpp를 사용했다면 조금 더 수월했을 것 같은데, 문자열 비교에 substring을 계속 생성하고 compare하는 과정이 많은 시간을 소요하지 않았나 싶다.
일단 더러운 코드의 원본을 확인하자. IDE 상에서 테스트 했던 코드 전부를 첨부한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class App {
public static void main(String[] args) {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s = "";
int result = 0;
try {
s = bf.readLine();
} catch (IOException e) {
System.out.println(e);
}
result = solution(s);
System.out.println("s = " + s);
System.out.println("result = " + result);
}
public static int solution(String s) {
int len = s.length();
int answer = len; // 최초 값 : 문자열 길이만큼
for (int groupSize = 1; groupSize < len; groupSize++) {
String newAnswer = ""; // 압축한 문자열
String before = s.substring(0, groupSize); // 비교 할 문자 그룹
String compare; // index 위치의 그룹
int index = 0; // 확인 중인 위치
int count = 0; // 반복된 그룹 갯수
try {
for (index = 0; index < len; index += groupSize) {
compare = s.substring(index, index + groupSize);
// System.out.println("compare = " + compare);
// System.out.println("before = " + before);
if (before.equals(compare)) {
// 두 문장이 같으면
count++; // 반복 횟수 증가
}
else {
// 두 문장이 다르면
if (count == 1) {
// 1번 등장했다면 반복 없는 것이므로
// 1(문자열) 이 아닌 (문자열)을 붙임
newAnswer += before;
}
else {
// 2번 이상 등장시에는
// 반복횟수 + 문자열 을 붙임
newAnswer += Integer.toString(count) + before;
}
// 다시 다음 그룹을 비교하기 위해 초기화
count = 0; // 반복 횟수 0
before = compare; // 이제 현재 위치의 그룹을 비교하기로 함
index -= groupSize; // 다시 현재의 위치부터 비교 시작
// System.out.println("newAnswer = " + newAnswer);
// System.out.println();
}
}
} catch (Exception e) {
// groupSize단위로 비교 중에, 마지막에 groupSize보다 단어가 부족할 시에
// point Over로 인한 익셉션 발생, 작업 종료로 쓰임. 익셉션에 따른 별도 작업 없음
}
// 익셉션으로 빠져나왔기 때문에, 마무리 작업을 해준다.
// 마지막까지 비교한 그룹에 대해 처리한다
// 위와 마찬가지로, 1회일 경우에는 (횟수) + 문자열
// 아닌 경우에는 문자열만 더해준다
if (count != 1) {
newAnswer += Integer.toString(count) + before;
}
else {
newAnswer += before;
}
// groupsize보다 반복 size보다 작은 애들 처리.
// 그냥 남은 문자열을 그대로 더해준다
newAnswer += s.substring(index);
// System.out.println("최종 newAnswer = " + newAnswer);
// System.out.println();
// System.out.println();
// System.out.println();
if (newAnswer.length() < answer) {
answer = newAnswer.length();
}
}
return answer;
}
}
위의 코드는 문자열의 길이만 처리하는 것이 아니고, 압축된 문자열을 만들어서 길이를 비교하도록 짰다. 우선 이렇게 작성한 후, 후에 길이만 비교하도록 변경했다.
이 복잡한 코드를 보고 읽을 수 있는 사람은 없을 것 같다.. 일단 설명을 하자면,
1) 문자열을 그룹별로 나누기 위한 길이를 groupSize로 정한다.
2) 이후 몇번 등장하는지 비교하는 용도로 쓰일 String before와, index를 통해 다음 그룹으로 계속 넘어가면서 before와 비교될 String compare가 있다. compare는 index를 따라 계속 넘어가며 비교하고, before와 다를 시에는 이전에 반복된 갯수와 그룹을 String newAnswer에 저장한다.
3) 이렇게 반복되다보면, 마지막 그룹 이후에는 compare에 할당되어야할 문자열이 groupSize보다 문자열의 길이가 부족할 때가 있다. (처음 입력받은 문자열의 길이가, groupSize로 나누어 떨어지지 않는다면 발생하는 문제이다. 예를 들면, "abcde"일 때, groupsize가 2라면 ab cd e 로 나뉜다. 여기서 compare가 c로 할당될 때 index가 문자열의 길이를 넘어서면서 익셉션이 발생한다.) 여기서의 익셉션을 종료 신호로 사용하고 처리한다.
4) compare를 새로 할당할 때 익셉션이 발생하기 때문에, 마지막까지 비교했던 before가 얼마나 반복됐는지는 newAnswer에 반영되지 못했다. 때문에 이것을 우선 처리해준 후, group에 해당하지 못한 문자열을 더해준다.
5) 이렇게 최종적으로 newAnswer가 완성되면, 해당 문자열의 길이를 기존의 answer와 비교해서 작은 값을 반환한다.
로 복잡한 과정을 거쳐 결과를 만들었다.
이제 이 코드에서 String newAnswer을 만들지 않고 int newAnswer로 길이만 저장하게끔 변경해주면 된다. 변경 사항으로는
- newAnswer += groupSize; 혹은 (반복횟수의 자릿수) + groupSize;
- 마지막 group에 포함되지 못한 문자열도 s.substring(index).length()을 더한다.
특히 (반복횟수의 자릿수)는 29는 +1, 1099는 +2 처럼 문자열 길이만큼만 더해줘야한다. 이를 처리하기 위해 Integer.toString(count).length()이라는 함수로 길게 처리했다.
결론적으론 아래의 형태로 제출하면서, 압축된 문자열을 만드는 것보단 조금 시간을 아껴서 제출했다.
public static int solution(String s) {
int len = s.length();
int answer = len; // 최초 값 : 문자열 길이만큼
for (int groupSize = 1; groupSize < len; groupSize++) {
int newAnswer = 0;
String before = s.substring(0, groupSize);
String compare;
int index = 0;
int count = 0;
try {
for (index = 0; index < len; index += groupSize) {
compare = s.substring(index, index + groupSize);
if (before.equals(compare)) {
count++;
}
else {
if (count == 1) {
newAnswer += before.length();
}
else {
newAnswer += Integer.toString(count).length() + groupSize;
}
count = 0;
before = compare;
index -= groupSize;
}
}
} catch (Exception e) { }
if (count != 1) {
newAnswer += Integer.toString(count).length() + groupSize;
}
else {
newAnswer += groupSize;
}
newAnswer += s.substring(index).length();
if (newAnswer < answer) {
answer = newAnswer;
}
}
return answer;
}백준처럼 실행 시간이 딱 나오진 않지만, 결과 뜨는 화면이 느린 걸로 보아 시간이 많이 소요됐을 것으로 보인다.
어서 모범 답안을 확인하자.
모범 답안
class Solution {
public int solution(String s) {
int answer = 0;
for(int i=1; i<=(s.length()/2)+1; i++){
int result = getSplitedLength(s, i, 1).length();
answer = i==1 ? result : (answer>result?result:answer);
}
return answer;
}
public String getSplitedLength(String s, int n, int repeat){
if(s.length() < n) return s;
String result = "";
String preString = s.substring(0, n);
String postString = s.substring(n, s.length());
// 불일치 -> 현재까지 [반복횟수 + 반복문자] 조합
if(!postString.startsWith(preString)){
if(repeat ==1) return result += preString + getSplitedLength(postString, n, 1);
return result += Integer.toString(repeat) + preString + getSplitedLength(postString, n, 1);
}
return result += getSplitedLength(postString, n, repeat+1);
}
}재귀 함수를 통해 처리했다. 재귀를 통해 처리하되, 각 문자열 반복에 대한 비교는 String.startsWith("문자열")을 통해 처리했다. 앞의 preString이 반복된다면 다시 이 문자열을 잘라서 재귀 시키고, 그게 아니라면 repeat값을 붙여서 반환해주었다. n이 그룹의 크기로서 대입하게 되는데, 이 n의 크기 제한을 for(int i=1; i<=(s.length()/2)+1; i++)로 처리하여
그 이상은 반복이 불가능하므로 적절하게 제한했다.
이 코드를 보면서 나의 코드를 보자면
startsWith()을 알았다면 그나마 나의 코드도 더욱 깔끔해졌을 것이다- 그룹의 크기를
s.length()/2로만 제한했어도 불필요한 반복을 줄였다 - 압축된 문자열을 완성시킴에도 나의 코드보다 빠르다
앞으로 다른 문제 풀 때는 일일히 substring으로 비교하지 말고 startsWith()을 통해 비교해야겠다. 참고링크(startsWith(),endsWith())
class Solution {
public int solution(String s) {
int min = s.length();
int len = s.length()/2+1;
for(int i = 1; i < len; i++) {
String before = "";
int sum = 0;
int cnt = 1;
for(int j = 0; j < s.length();) {
int start = j;
j = (j+i > s.length()) ? s.length():j+i;
String temp = s.substring(start, j);
if(temp.equals(before)) {
cnt++;
} else {
if(cnt != 1) {
sum += (int)Math.log10(cnt)+1;
}
cnt = 1;
sum+=before.length();
before = temp;
}
}
sum+=before.length();
if(cnt != 1) {
sum += (int)Math.log10(cnt)+1;
}
min = (min > sum) ? sum : min;
}
return min;
}
}위 코드도 나의 코드보다는 간결하다. 반복된 횟수의 자릿수 계산을 위해 Math.log10(cnt)를 사용한 점이 인상깊다.