[LeetCode - 271] encode and decode strings - C++

분류: 문자열 /

 

문제

271. String Encode and Decode

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.

Please implement encode and decode

 

Example 1:

Input: ["neet","code","love","you"]
Output: ["neet","code","love","you"]

Example 2:

Input: ["we","say",":","yes"]
Output: ["we","say",":","yes"]

Constraints:

`0 <= strs.length < 100`
`0 <= strs[i].length < 200`
`strs[i]` contains only UTF-8 characters.

 

풀이

class Solution {
public:

    string encode(vector<string>& strs) {
        string ans = "";
        for(const string &str:strs) 
            ans += to_string(str.size()) + ":" + str;
        return ans;
    }

    vector<string> decode(string s) {
        vector<string> ans;
        int i = 0, len = s.size();
        while(i < len) {
            int start = i;
            while(s[i] != ':') i++;
            int length = stoi(s.substr(start, i++ - start));
            ans.push_back(s.substr(i, length));
            i += length;
        }
        return ans;
    }
};

 

두개의 함수를 구현해 `output = decode(endcode(input))`일 때 `output == input`인 단방향 역원을 구현하는 점이 재밌는 문제였다.

백준은 출력, 프로그래머스는 하나의 함수를 구현하는 형태의 문제지만 릿코드는 조금 더 다양한 문제가 있는것 같다.

`encode`를 구현하는 것은 아주 쉽다. 구분자(delimiter)를 끼워넣어 합치면 된다. 여기서 문제는 `decode`에서 발생한다.

입력값은 모두 UTF-8 문자이므로 구분자가 포함된 입력이 들어올 경우 문제가 발생한다.

 

예시)

input = ["a,b"], delimiter = ','

output = ["a", "b"]

 

구분자를 입력값에서 등장할 확률이 매우 낮게 설정할 수도 있을 것이다. 예를들어 `"ㄱ@#a%ㅂㅁ^!#$%ㅍ@$#!ㅏ#$;_!#$%(!"` 와 같이 말이다. 아마 아주 긴 구분자를 사용한다면 테케는 통과할 것 같다.

 

하지만 이는 뭔가 찝찝한 느낌이 들것이다. 긴 구분자를 사용할 경우 인코딩 문자열이 아주 길어진다는 단점과 결국 확률에 의존해야한다는 단점이 있다. 어떻게 하면 UTF-8 문자를 이용한 구분자를 이용해 문자열로 인코딩하고 원본으로 디코딩 할 수 있을까?

 

키는 단순히 같은 구분자를 사용하는 것이 아니라 구분자에 정보를 담는 방법이다. 인코딩하는 문자열의 숫자를 적고 그 뒤에 문자열을 붙인다. 

예시)

input = [ "aaa", "1234" ]

encoded = "3:aaa4:123"

여기서 문자열의 길이와 문자열 사이에 `:`를 넣는 이유는 문자열이 숫자로 시작하는 경우 어디까지가 메타 데이터이고 어디서부터 데이터인지 알 수 없기 때문이다.