프로그래머스 압축 Java - 최적화하기

https://school.programmers.co.kr/learn/courses/30/lessons/17684

프로그래머스

2018 KAKAO BLIND RECRUITMENT

코딩테스트 연습 | 프로그래머스 스쿨

 

<2018년도 카카오 블라인드 채용 기출 [3차]>

 

위의 문제를 이전에 풀어봤을 땐 5일씩 붙잡고 풀었던 기억이 난다. 

여러 가지 노하우가 쌓인 지금 HashMap과  StringBuilder를 사용해서 다시 풀어봤다.

 

 

구현 착안

 

 

(최적화 전 -> 최적화 후)

ArrayList -> HashMap 사용

String + 더하기 연산 -> StringBuilder 사용

 

최적화 하기 전 코드

import java.util.ArrayList;

class P압축 {
    public ArrayList<Integer> solution(String msg) {
        // TOBEORNOTTOBEORTOBEORNOT
        /*
        T[20] O / TO : 27
        O[15] B / BO : 28
        B[2] E / BE : 29
        E[5] O / EO : 30
        O[15] R / OR : 31
        R[18] N / RN : 32
        N[14] O / NO : 33
        O[15] T / OT : 34
        T[20] T / TT : 35
        TO[27] B / TOB : 36
        BE[29] O / BEO : 37
        OR[31] T / ORT : 38
        TOB[36] E / TOBE : 39
        EO[30] R / EOR : 40
        RN[32] O / RNO : 41
        OT[34]
        */

        // 문자열을 압축한 후의 사전 색인 번호
        ArrayList<Integer> answer = new ArrayList<>();

        // 사전
        ArrayList<String> alphabet = new ArrayList<>();

        // 사전 초기화
        for(int i = 0; i < 26; i++) {
            alphabet.add(Character.toString((char) (i + 65)));
        }

        int remain = 0;

        for(int i = 0; i < msg.length(); i++) {
            String w = "";
            String str = "";

            // 현재 인덱스에 해당하는 문자를 한 글자를 str 담는다.
            str += msg.charAt(i);

            for(int j = i + 1; j < msg.length(); j++) {
                // str을 w에 저장한다.
                w = str;

                // str에 그 다음 한 글자를 더 붙인다.
                str += msg.charAt(j);

                if(!alphabet.contains(str)) { // str이 새로운 단어라면
                    alphabet.add(str); // 사전에 str을 등록한다.

                    /* 중요 */
                    if(w.length() > 1) i += w.length() - 1; // w이 두 글자 이상이면 i 인덱스가 (글자 길이 - 1)에 가게 한다.

                    remain = i; // i 인덱스를 remain에 잠시 저장한다. (마지막으로 처리되지 않은 글자)

                    answer.add(alphabet.indexOf(w) + 1); // 사전에서 w의 색인 번호를 찾아 정답 배열에 담는다.

                    break;
                }
            }
        }

        String lastStr = "";

        // 입력이 길이가 1인 문자열일 때
        if(msg.length() == 1) {
            answer.add(1);
        } else {
            // 길이가 2 이상의 문자열은 위의 로직을 거치고 옴
            // 마지막 남은 글자 answer에 추가
            for(int i = remain + 1; i < msg.length(); i++) {
                lastStr += msg.charAt(i);
            }

            // 새로운 단어는 위의 로직에서 모두 등록을 마쳤기 때문에
            // lastStr은 무조건 사전에 등록된 단어이다.
            answer.add(alphabet.indexOf(lastStr) + 1);
        }

        return answer;
    }

    public static void main(String[] args) {
        P압축 p = new P압축();

        System.out.println(p.solution("TOBEORNOTTOBEORTOBEORNOT"));
    }
}

 

 

최적화 후 코드

import java.util.ArrayList;
import java.util.HashMap;

class P압축_최적화 {
    public ArrayList<Integer> solution(String msg) {
        // 문자열을 압축한 후의 사전 색인 번호
        ArrayList<Integer> answer = new ArrayList<>();

        // 사전
        HashMap<String, Integer> alphabet = new HashMap<>();

        // 사전 초기화
        for(int i = 0; i < 26; i++) {
            alphabet.put(Character.toString((char) (i + 65)), i + 1);
        }

        int remain = 0;

        for(int i = 0; i < msg.length(); i++) {
            StringBuilder w = new StringBuilder();
            StringBuilder str = new StringBuilder();

            // 현재 인덱스에 해당하는 문자를 한 글자를 str 담는다.
            str.append(msg.charAt(i));

            for(int j = i + 1; j < msg.length(); j++) {
                // str을 w에 저장한다.
                w.setLength(0);
                w.append(str);

                // str에 그 다음 한 글자를 더 붙인다.
                str.append(msg.charAt(j));

                if (!alphabet.containsKey(str.toString())) { // str이 새로운 단어라면
                    alphabet.put(str.toString(), alphabet.size() + 1); // 사전에 str을 등록한다.

                    if(w.length() > 1) i += w.length() - 1; // w이 두 글자 이상이면 i 인덱스가 (글자 길이 - 1)에 가게 한다.

                    remain = i; // i 인덱스를 remain에 잠시 저장한다. (마지막으로 처리되지 않은 글자)

                    answer.add(alphabet.get(w.toString())); // 사전에서 w의 색인 번호를 찾아 정답 배열에 담는다.

                    break;
                }
            }
        }

        // 입력이 길이가 1인 문자열일 때
        if(msg.length() == 1) {
            answer.add(1);
        }

        // 마지막 글자 처리
        if (remain < msg.length() - 1) {
            String lastStr = msg.substring(remain + 1);
            answer.add(alphabet.get(lastStr));
        }

        return answer;
    }

    public static void main(String[] args) {
        P압축_최적화 p = new P압축_최적화();

        System.out.println(p.solution("TOBEORNOTTOBEORTOBEORNOT"));
    }
}

 

 

w.setLength(0);
w.append(str);

여기서 StringBuilder는 대입 연산이 되지 않기 때문에 setLength(0)로 StringBuilder 변수를 초기화하고 append 해줘야 한다.

 

 

제출 결과

문제 풀이 최적화 결론

1. 문자열 조작 시 문자열을 더하는 것 보다 StringBuilder를 사용하는 편이 좋다.
2. 기존의 alphabet.contains(str)로 중복 확인을 하면 O(n) 시간이 걸릴 수 있다. ArrayList 대신 HashMap을 사용하여 O(1)의 시간복잡도로 조회할 수 있다.

 

최적화 후(HashMap, StringBuilder)가 최적화 하기 전(ArrayList에서 조회, String + 더하기 연산)보다 약 1/10배의 시간을 줄여준 것을 확인할 수 있었다.