Blind 75 Must do Leetcode: Encode and Decode Strings

Blind75는 Leetcode의 문제들 중 소프트웨어 엔지니어 인터뷰 준비에 유용한 75개의 문제를 선정한 것을 말한다. Blind75는 배열, 문자열, 링크드 리스트, 트리, 그래프, 정렬, 다이나믹 프로그래밍 등 다양한 알고리즘과 자료구조를 포함하고 있다. 따라서 이 목록은 인터뷰 준비를 체계적으로 하고자 하는 사람들에게 방향을 제시해 주며, 실제 인터뷰에서 자주 출제되는 유형의 문제들을 연습할 수 있게 해 준다.

 

Blind 75 문제를 하루에 한 문제씩 풀어보면서 코딩 테스트 감을 유지해보려고 한다. Blind 75 풀어보기 시리즈 세번째 문제는 Encode and Decode Strings다. https://leetcode.com/problems/encode-and-decode-strings

LeetCode - The World's Leading Online Programming Learning Platform

이 문제는 주어진 문자열 배열을 하나의 문자열로 직렬화하는 encode 함수, 그리고 직렬화된 문자열을 다시 원래의 문자열 배열로 돌려주는 decode 함수를 구현하는 것이다. 문제의 조건으로 문자열은 유니코드가 아닌 아스키 문자열로 제한한다.

문자열 배열을 하나로 합치고 다시 원래의 문자열 배열로 복구하려면 무엇이 필요할까? 바로 원본 문자열을 구분할 수 있는 구분자(delimeter)가 필요하다. 그럼 어떤 구분자를 선택할 수 있을까? 문자열이 아스키 문자열로 제한되기 때문에 유니코드 구분자를 쓸 수 있다. 원본 문자열과 구분되는 구분자를 써야만 decode시 원본 문자열을 그대로 복구할 수 있다. 예를 들어, 구분자로 쓰이는 문자가 원본 문자열에 포함되어 있다면 원본 문자열이 두 개로 쪼개질 수 있다.

그런데 아스키 코드 중에서도 실제로 쓰이지 않는 코드들이 있다. 이 코드는 억지로 넣지 않는 한 사용되지 않는 코드라서 사용자의 입력으로 나오지 않는다고 기대할 수 있다. 

구분자를 선정하고 나면 구현은 크게 어려울 것이 없다.

encode 함수의 경우, StringBuilder 객체를 생성한다. 그리고 리스트를 순회하면서 문자열을 append 하고 구분자를 append 한다. 그리고 마지막 문자열 뒤에는 구분자를 넣지 않는다. 마지막 문자열 입력 뒤에 구분자가 들어가면 decode시 원본 문자열 중에 빈 문자열이 있다고 생각할 수 있기 때문이다.

decode 시에는 indexOf() 함수를 활용한다. indexOf 함수는 문자열에서 구분자가 있는 인덱스를 알려주는데, 두 번째 파라미터를 통해서 문자열의 어떤 위치부터 검색할지 선택할 수 있다. 그래서 구분자의 검색 범위인 from을 0으로 초기화하고, 구분자를 찾아서 i에 할당한다. 그러면 원본 문자열은 [from, i) 범위의 부분 문자열이 된다. 그러면 다음 구분자를 찾기 위해 from을 i+1로 할당하고 다음 구분자를 찾아서 원본 문자열을 찾고 결과 리스트에 넣는 작업을 반복한다.

설명한 로직을 자바 코드로 짜면 아래와 같다.

public class Codec {

    private char delimeter = 0x81;

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<strs.size(); i++) {
            String s = strs.get(i);
            sb.append(s);
            if (i != strs.size()-1) {
                sb.append(delimeter);
            }
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> ret = new ArrayList<>();
        int from = 0;
        int i = s.indexOf(delimeter, from);
        while(i != -1) {
            ret.add(s.substring(from, i));
            from = i+1;
            i = s.indexOf(delimeter, from);
        }
        ret.add(s.substring(from));
        return ret;
    }
}

다음 로직의 시간 복잡도, 공간 복잡도를 계산해보자.encode의 시간 복잡도는 문자열 리스트를 순회하기 때문에 O(n)이고, 결과 문자열을 공간 복잡도 계산에 포함한다면, n개 문자열에 구분자가 n-1개 추가로 포함된다. 그래서 O(n + n-1) = O(n)이 된다.decode의 시간 복잡도는 원본 문자열이 n개라고 가정할 때 n번 작업을 반복하므로 O(n)이다. 그리고 결과 리스트가 n개 문자열을 저장하므로 공간복잡도도 마찬가지로 O(n)이 된다.

 

Blind75 포스팅 모음 https://codeendeavor.tistory.com/tag/blind75