구현
프로그래머스 2020 KAKAO BLIND RECRUITMENT Level 2 문제 문자열 압축을 Java를 이용해 풀어보았다.
결국 풀기는 했지만 내 풀이는 너무나 초라하다. ㅎ... 멋진 풀이가 많았고 본질만 건드리는 풀이가 참 매력적이었다.
일단 거지가튼 내 풀이부터 먼저 살펴볼까? 아님 좋은 풀이를 설명하면서 내가 공부를 할까... 다 해야겠다(의식의 흐름)
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/60057
잘린 문자열 비교하며 결과 문자열 만들기
Integer compressor(int n, String s) 라는 메소드를 선언해서 n자리 짜리로 s를 잘라서 만든 결과 문자열의 길이를 반환하는 형식으로 풀었다.
일단 큐 하나를 선언해서 원본 문자열의 앞에서부터 n자리만큼 잘라 넣는다. 이 작업만 먼저 살펴보면 다음과 같다.
Queue<String> q = new LinkedList<>();
int i=0;
while(i<s.length()){
if(i+n<=s.length()) q.add(s.substring(i, i+n));
else q.add(s.substring(i));
i += n;
}자릿수만큼 잘라서 큐를 완성했다면 이제 하나씩 꺼내가며 이전 것과 비교해주는 작업을 진행하면 된다.
prev와cur이 동일하면i++- 서로 다르면 다음 두 가지 경우로 나뉨
(1)i==1이면prev만 붙여주기
(2) 아니면i+prev붙여주기- 가장 마지막에 큐에서 튀어나온 녀석은 작업이 종료된 이후에 붙여주자
이를 코드로 표현하면 다음과 같다.
i=1;
String prev = q.poll();
while(!q.isEmpty()){
String cur = q.poll();
if(cur.equals(prev)) i++;
else{
if(i==1) sb.append(prev);
else sb.append(i+prev);
i = 1;
}
prev = cur;
if(q.size()==0){ // 마지막 녀석 처리해주기
if(i==1) sb.append(cur);
else sb.append(i+cur);
}
}위의 두 코드들을 합치면 compressor 메소드가 완성된다. 다음과 같다.
static Integer compressor(int n, String s) {
StringBuilder sb = new StringBuilder();
Queue<String> q = new LinkedList<>();
int i=0;
while(i<s.length()){
if(i+n<=s.length()) q.add(s.substring(i, i+n));
else q.add(s.substring(i));
i += n;
}
i=1;
String prev = q.poll();
while(!q.isEmpty()){
String cur = q.poll();
if(cur.equals(prev)) i++;
else{
if(i==1) sb.append(prev);
else sb.append(i+prev);
i = 1;
}
prev = cur;
if(q.size()==0){
if(i==1) sb.append(cur);
else sb.append(i+cur);
}
}
return sb.toString().length();
}그러면 이 메소드를 n값만 바꿔가며 매번 몇 자리가 나오는지 확인해서 이전보다 더 작으면 갱신해주는 방식으로 최소 자릿수를 구하면 된다.
int solution(String s) {
int answer = s.length();
int len = s.length();
for (int i = 1; i <= len / 2; i++) { // 적어도 두 번 반복은 시킬만큼까지 잘라야 한다
int res = compressor(i, s);
answer = (res < answer ? res : answer);
}
return answer;
}다음은 내가 제출한 전체 코드다.
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class StringCompress {
static int solution(String s) {
int answer = s.length();
int len = s.length();
for (int i = 1; i <= len / 2; i++) {
int res = compressor(i, s);
answer = (res < answer ? res : answer);
}
return answer;
}
static Integer compressor(int n, String s) {
StringBuilder sb = new StringBuilder();
Queue<String> q = new LinkedList<>();
int i=0;
while(i<s.length()){
if(i+n<=s.length()) q.add(s.substring(i, i+n));
else q.add(s.substring(i));
i += n;
}
i=1;
String prev = q.poll();
while(!q.isEmpty()){
String cur = q.poll();
if(cur.equals(prev)) i++;
else{
if(i==1) sb.append(prev);
else sb.append(i+prev);
i = 1;
}
prev = cur;
if(q.size()==0){
if(i==1) sb.append(cur);
else sb.append(i+cur);
}
}
return sb.toString().length();
}
public static void main(String[] args) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
String s = "abcabcabcabcdededededede";
int ans = solution(s);
bfw.write(ans + "");
bfw.close();
}
}문자열을 구하지 말고 자릿수만 생각하기
결국 중요한 건 반환되는 String이 뭐냐가 중요한 게 아니라 자릿수가 중요한 거다. 프로그래머스의 다른 사람들의 풀이 중 자릿수만 계산한 풀이가 있던데 본질만 건드려서 잘 푼 풀이같다.
위의 풀이가 너무 거지같다는 생각이 들면 다음 풀이를 보며 이해하면 좋을 것 같다.
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;
}
}오직 자릿수만 계산해나가는 작업이라는 걸 염두에 두고 보면 좀 더 이해가 쉬울 것 같다.
오늘 배운 것
문제의 본질만 건드리는 풀이를 고민해보도록 하자
2022.03.10 재시도 ( 실패 )
처음에는 풀었는데 오히려 이번에는 몇몇 테스트 케이스를 통과하지 못했다. 이전에 풀었던 풀이와 새로 푼 풀이를 비교해보면 로직 자체는 맞는 것 같은데... 일단 5번 테스트 케이스 "a"를 고려하지 않아서 하나 틀렸고 몇 개 더 틀린 게 있었다. 왜 틀렸는지 깊이 고민하지 않았다...
아래는 새롭게 푼 풀이다.
import java.io.*;
import java.util.*;
public class StringCompress {
static ArrayList<Integer> list = new ArrayList<>();
static int solution(String s){
if(s.length()==1) return 1;
for(int i=1; i<=s.length()/2; i++){
compress(i, s);
}
Collections.sort(list);
return list.get(0);
}
static void compress(int n, String s){
StringBuilder sb = new StringBuilder();
Queue<String> q = new LinkedList<>();
int i=0;
while(i<s.length()){
if(i+n<=s.length()) q.add(s.substring(i, i+n));
else q.add(s.substring(i));
i += n;
}
i=1;
String prev = q.poll();
while(!q.isEmpty()){
String cur = q.poll();
if(cur.equals(prev)) i++;
else{
if(i==1) sb.append(prev);
else sb.append(i).append(prev);
i = 1;
}
prev = cur;
if(q.size()==0){
if(i==1) sb.append(cur);
else sb.append(i).append(cur);
}
}
list.add(sb.toString().length());
}
public static void main(String[] args) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
String s = "a";
int ans = solution(s);
bfw.write(ans + "");
bfw.close();
}
}