[코딩테스트 #1] 문자열 압축(2020 KAKAO BLIND RECRUITMENT) level1 - java

자기 발전을 위해서 1월 말을 기점으로 코딩테스트 연습을 시작하기로 하였다. 

 

무언가를 하기 위한 코딩을 정말 오랜만이라 기본 라이브러리나 메서드, 함수 등이 생각이 나지도 않은 상태에서 다시 코딩을 하려니 뭔가 막막한 기분이 들었다. 심지어 java print도 System.out.println이 기억나지도 않았고 대략 이런기능의 메서드가 있었던거 같은데?? 하는 기분으로 메서드 검색을 해가며 문제를 풀었다.

 

 

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

 

코딩테스트에 여러가지가 있겠지만 프로그래머스에 올라와 있는 level1의 문제들부터 차근차근 풀어보기로 했다. 

 

가장 처음 푼 문제는 평균 구하기였는데 이건 말도 안되게 간단한 문제로 코딩테스트가 이런거구나 하는 느낌을 느껴주게하는 연습문제였다.

 

 

그 다음에 이제 문제를 고른 것이 바로 2020 카카오 블라인드 채용에 기출되었던 5문제 중 1번 문제인 문자열 압축 문제였다. 얼마나 어렵겠어? 하고 자정 12시에 패기롭게 코딩을 시작.

5시간이 지난 오전 5시에 76점을 획득하였다. 완벽하다고 생각한 코드가 예문 전체 28번까지 중에 20~27번까지를 해결하지 못하고 있었다. 

 

다음날 다시 밤 11시에 어제 코드를 뒤로 남겨두고 다시 새롭게 코딩을 시작했다. 1시간 후 결과는 66점... 오히려 점수가 더 떨어졌었다. 한참을 디버깅하였고 문제점을 알아냈으나 해결할 수가 없었다.

 

다시 처음 코드를 가져왔다. 76점짜리 코드..

 

근데 다시 보니 그냥 눈에 보였다. 어? 설마 이걸 안해줘서 그런가?? 단 한줄 for문 안에 변수 입력을 하자 거짓말처럼 100점이 떴다.

 

뿌듯.. 고작 한문젠데

 

문제를 풀고 다른 사람들 코드를 보니 내코드가 너무 형편없어 보였다...  밑은 내 코드에 대한 약간의 설명이다.

 

class Solution {
        public int solution(String s) {
            int answer = 0;
            String ss = s;  // for문을 돌리기 위해 공백을 추가하기 위한 새로운 문자열 선언
            int num = 1;  // 패턴이 몇번 나오는지

            if(s.length() == 1){
                return 1;
            }

            // 압축할 단위
            for (int i = 1; i < s.length(); i++) {

                ss = s;  // 문제의 한 줄 (해당 라인을 추가하자 76점이 100점이 되었다.)
                
                for (int j = 0; j < i; j++) {  // substring을 활용하기 위해 공백 두 칸씩 추가
                    ss = ss + "  ";
                }

                String a = "";  // 압축할 단위 문자
                String b = ""; // 압축한 결과

                String string_com = s.substring(0, i);  // 처음부터 압축할 단위까지의 문자열

                for (int k = 0; k < s.length(); k += i) {
                    if (ss.length() > k + i + i) {
                        a = ss.substring(k, k + i);
                        if (ss.substring(k, k + i).equals(ss.substring(k + i, k + i + i))) {  // 같애??  다음이다음이 없을수도있음
                            num++;
                        } else {  // 틀렸네?
                            if (num == 1) {
                                b = b + a;
                            } else {
                                b = b + Integer.toString(num) + a;
                                num = 1;
                            }
                        }
                    }
                }

               
                b = b.trim();  // 공백을 제거
                //System.out.println(b);
                //System.out.println(b.length());

                if (i == 1) {
                    answer = b.length();
                } else {
                    if (answer > b.length()) {
                        answer = b.length();
                    }
                }
            }

            return answer;
        }

    }

 

총 이 한 문제를 100점 맞기까지 순수 시간만 7시간 걸린거 같다. 이제 시작이니까 천천히 준비해야겠다.

 

문제에 대한 접근은 다음과 같은 순서로 진행했다.

 

1. 압축할 숫자의 단위 

  - 1부터 문자열의 길이 전까지 압축할 숫자의 단위를 for문으로 반복해야겠다라고 생각했고 마지막에 answer에 대한 비교문을 넣어야 겠다고 생각했다.

 

2. 처음부터 압축할 단위에 맞춰 문자열을 자르기 

  - 압축할 숫자의 단위를 정했으면 그 다음엔 전체 문제를 압축숫자단위에 따라 자르고 비교해야겠다고 생각했다.

 

3. 위를 기준으로 기초 베이스를 만들고 나서 오류를 해결하기 시작했다.

 

4. 가장 거슬렸던 오류는 substring의 범위이다. 내가 만든 코드의 특성상 (굉장히 지저분하다) 최적화가 되어있지 않기 때문에 substring으로 문자를 잘라야하는데 문자의 length보다 긴 범위가 선택되버리면 어김없이 인덱스에러가 나버렸다. 

 

이를 해결하기 위해서 여러가지를 생각해봤다. for문이 3개 4개 if else문이 3개, 4개 굉장히 복잡한 코드가 되었는데 결론적으로 이렇게 생각을했다. 

 

어차피 범위가 없기때문이라면 범위를 만들어주면되지않을까? 

 

그래서 공백의 범위를 문자열 뒤에 추가해 줌으로써 해당에러를 해결했다. 덕분에 코드는 이전보다 간단해졌다. 물론 속도적인 측면에선 공백인 칸이 늘어났기 때문에 시간이 늘어났을 수도 있으나 (지금 이 글을 쓰는 와중에 if문으로 k의 문자가 공백일 때 for문을 빠져나오는 break를 추가하면 속도도 늘어날 수 있을거 같다는 생각이 났다.) 결론적으로 풀었으니 해결한 거 아닐까? 

 

 

화이팅!