모각코 PS / 카카오 2020 신입 블라인드 채용 1차 문자열 압축

모각코 PS스터디

왜인지 모르겠는데 PS는 하고 나서 포스팅 하는 걸 자꾸 까먹는다.
이번주 스터디 한 세 문제를 차례로 포스팅해보려고 한다.

문제와 풀이

---

문제 링크 : 카카오 2020 신입 개발자 블라인드 채용 1차 코딩 테스트 - 문자열 압축
해당 문제는 프로그래머스에서도 풀어볼 수 있다.

👇펼쳐서 코드와 해설 읽기

문자열 카테고리의 문제다.
로직 자체는 매우 직관적으로 떠올릴 수 있다.
머릿속으로 비교하는 그림이 대강 그려졌다.

대충 이렇게.

딱 봐도 뭔가 반복문을 겹겹이 돌아야할 것 같은 기분이 든다(표본 길이가 최대 1000이니까 낭낭히 돌아도 문제 없다).

그래서 코드를 짜기 전에 '어떤 반복문을 / 어떤 범위로 / 얼마만큼씩 키워나가면서' 돌 것인지 정리를 하고 구현을 시작했다.

어떤 반복문을	어떤 범위로	얼마만큼씩 키워나가면서
기준문자열의 길이를 늘려나가기 위한 loop	원하는 길이의 범위는 1 ~ length()/2	1자씩 늘려나갈 것
기준문자열을 이동하기 위한 loop	? ~ length()	기준문자열 길이만큼씩 늘려나갈 것
비교문자열을 이동하기 위한 loop	? ~ length()	기준문자열 길이만큼씩 늘려나갈 것

꼭 구체적으로 생각나지 않아도 된다. 명확히 시작/조건/증감이 떠오르면 그대로 for문을 작성하면 되고, 아닌 경우는 while문을 써줘도 되기 때문이다.
특히나 안쪽의 두 반복문은, 조건을 공유하거나 초기변수를 공유할 것 같은 생각이 강하게 들었다.

짜보면 알겠지. (설명이 필요하다고 생각되는 부분은 가능한 한 주석으로 남겼다.)

아!
결국 문자열의 길이가 알고 싶은 거지 실제로 압축 문자열을 구하고 싶은 건 아니기 때문에, 압축된 문자열의 길이만 구했다. 설명 빼먹을 뻔 했네.

public class Week2_1 {

    public static void main(String[] args) {
        Week2_1 w = new Week2_1();
        System.out.println(w.solution("xababcdcdababcdcd"));
    }

    public int solution(String s) {
        int resultLength = s.length();

        for (int i = 1; i <= s.length() / 2; i++) { // 기준문자열의 길이를 늘려나가기 위한 loop
            int pos = 0; // (기준/비교)문자열의 시작 위치
            int compressLength = s.length();

            while (pos + i <= s.length()) { // 기준문자열을 이동하기 위한 loop
                String baseString = s.substring(pos, pos + i);

                int appear = 1; // 등장 횟수 (중복횟수 X)
                while (pos + i <= s.length()) { // 비교문자열을 이동하기 위한 loop
                    pos += i;
                    String compareString = pos + i <= s.length()
                            ? s.substring(pos, pos + i)
                            : null;

                    if (baseString.equals(compareString)) {
                        appear++;
                    } else {
                        if (1 < appear) {
                            compressLength -= i * appear;
                            compressLength += String.valueOf(appear).length(); // (int)Math.log10(appear) + 1
                            compressLength += baseString.length();
                        }
                        break;
                    }
                }

            }
            resultLength = Math.min(resultLength, compressLength);

        }

        return resultLength;
    }

}

마무리

---

위에서도 말했지만 로직 자체는 매우 직관적으로 떠올릴 수 있는 문제다.
떠올린 로직을 얼마나 빨리 구현할 수 있는 능력이 되는지를 보는 문제같다.
30분 컷 하면 적당하다고 한다.
물론 나는 알고린이기 때문에 3시간 정도 걸렸다. 그래도 3달전? 2달전?에 봤을때는 아예 풀지도 못했기 때문에, 그래도 발전이 있긴 있었다고 위안삼았다.

compressLength를 구하는 부분이나, 삼항연산하는 부분, 그런 곳은 따로 메서드를 뽑으면, 메인로직이 더욱 한 눈에 들어오게 깔끔해질 것 같다.

반복 loop 수를 줄일 수도 있으나, 코드가 더 복잡해질 거라고 생각이 되어서 별로 줄이고 싶지 않았다. 반복 loop 수가 3번이라고 O(n^3)이 되는 건 아니니까.
나에겐 내가 보기 좋고, 남이 읽기 쉬운 코드가 최고 좋은 코드다.

모든 반복문은 재귀로 대체할 수 있으니, 재귀를 써도 좋을 거 같다. 실제로 풀고 나서 다른 사람들의 풀이를 체크해보니 재귀를 써서 푼 코드가 제일 많았다.
성능이고 뭐고를 떠나서(코딩테스트는 성능테스트가 아니니까), 재귀로 고쳐보는 것은 재미난 경험이 될 것 같다.

마무리 2

---

그리고 사실 두번째 코드도 있다.
처음 이 문제를 풀려고 시도했을 때 작성했던 코드다(3달전?...쯤에).
'압축된 문자열의 길이'만 구하자는 생각을 못하고, 실제로 압축된 문자열을 만드는 로직이다.
사실 이렇게 해도 대부분 잘 돌아간다(훨씬 느리지만).

하지만...

👇펼쳐서 코드와 해설 읽기

하지만 카카오 코테의 특징은 테스트케이스가 굉장히 많고 가혹한 엣지케이스가 많다는 것이다.
실제로 두 케이스를 통과하지 못해서, 해당 테스트케이스가 어떤 경우인지 구글링해서 로직을 테스트해보았으나, 전부 통과했다.
????.....
사람들이 말하는 모든 조건은 다 통과했지만 테스트 사이트에서만 통과하지 못했다. (진짜 짜증나서 비슷한 문제들까지 이잡듯이 뒤졌었는데 결국 못 풀었었다 ㅋㅋㅋㅋ 하다하다 문제에다 화를 내네.. 성격 진짜 나쁜듯...)
실제 시험이면 탈락하고나서 좀 억울한 마음을 가졌을 것 같다.

'이 정도 문제는 이렇게도 후루룩, 저렇게도 후루룩 풀어버릴 수 있을 정도로 실력을 많이 쌓아야 카카오 무난히 갈 수 있는 거구나'란 기준을 알게 되었다.

class Solution {
    private int zippedNumber = 1;
    private StringBuilder zippedString;

    private boolean addZipNum(String cursor, String forwardCursor) {
        boolean tf = cursor.equals(forwardCursor);
        if (tf) zippedNumber += 1;
        return tf;
    }

    private void appendZipStr(String cursor) {
        if (zippedNumber == 1)
            zippedString.append(cursor);
        else
            zippedString.append(zippedNumber).append(cursor);
    }

    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        if (s.length() <= 2) return s.length();

        // 비교 기준이 되는 문자열을 커서, 비교할 대상이 되는 문자열을 포워드커서(i만큼 앞선 문자열)라고 부른다.
        // i : 반복할 커서의 길이. 한번의 대조가 끝날때마다 한 자리씩 늘린다.
        for (int i = 1; i <= s.length() / 2; i += 1) {
            zippedString = new StringBuilder();
            String cursor = s.substring(0, i); //최초 커서 초기화. 이후에는 내부 for문 속에서 갱신.
            String forwardCursor = null;

            // j : i개만큼씩 반복 비교하기 위해 문자열을 substring()할 때, slicing index를 담는 변수.
            int j = i;
            while (j <= s.length()) {

                if (j + i <= s.length()) {
                    forwardCursor = s.substring(j, j + i);

                    if (!addZipNum(cursor, forwardCursor)) {
                        appendZipStr(cursor);
                        this.zippedNumber = 1;
                        cursor = forwardCursor;
                    }
                }
                else {
                    appendZipStr(cursor);
                }

                j += i;
            }

            zippedString.append(s.substring(j - i));
            answer = answer > zippedString.length() ? zippedString.length() : answer;
        }

        return answer;
    }
}