880. Decoded String at Index

• 이 문제의 핵심은 만들어질 문자열에서 prefix를 효과적으로 잘라내는 방법을 고민하는 데에 있다.

• 먼저 문자열을 해석하여 반복될 문자열의 일부 value 와 지금까지 나왔던 pattern을 반복할횟수 repeat 를 구하여 각각을 구분되는 항목 Item으로 만든다.

• 그리고 각 항목의 문자열 범위를 계산한다.
• 반복 횟수 repeat 가 지정된 항목의 경우 from 에는 지금까지의 문자열 길이, to 에는 반복된 총 길이를 기록한다.
• 반복될 문자열의 일부 value 가 지정된 항목의 경우 from에는 지금까지의 문자열 길이, to 에는 value 가 더해진 총 문자열의 길이를 기록한다.

• 마지막으로 k 값을 0-based index로 변환 --k 하고 다음 작업을 반복적으로 수행한다.
• (1) k 를 포함하는 범위 [from, to) 를 가진 항목을 찾는다.
• (2-1) repeat가 지정된 항목이라면 k 에서 prefix의 길이 from을 나눈 나머지 k % from 를 새로운 k 값으로 한다.
• 검색할 위치 k 앞에는 from 길이 만큼의 prefix가 임의의 횟수만큼 반복될 수 있다.
• 이것을 잘라내고 나면 새로운 index k’는 결국 prefix 내부의 위치하게 된다.
• (2-2) value 가 지정된 항목이라면 k 에서 prefix의 길이 from 을 뺀 값을 새로운 k 값으로 하고 이를 기반으로 현재 항목의 값을 접근 item.value[k] 하여 결과로 돌려준다.
• prefix from 을 잘라내고 나면 새로운 index k’ 는 현재 항목의 문자열 value 내에 위치하게 된다.

class Solution {
public:
    struct Item {
        string value;
        int repeat;
        long long from;
        long long to;
    };

    string decodeAtIndex(string s, int k) {
        // make items
        vector<Item> items;
        for (auto c : s) {
            if (c >= '0' && c <= '9') {
                if (items.empty()) continue;
                items.push_back({{}, c - '0', 0});
            } else {
                if (items.empty() || items.back().repeat > 0) {
                    items.push_back({});
                }
                items.back().value += c;
            }
        }
        // calculate range
        long long prevLength = 0;
        for (auto& item : items) {
            item.from = prevLength;
            if (item.repeat > 0) {
                item.to = prevLength * item.repeat;
            } else {
                item.to = prevLength + item.value.length();
            }
            prevLength = item.to;
        }
        // to zero based index
        --k;
        int pos = 0;
        while (true) {
            // find matching range
            for (int i = 0; i < items.size(); ++i) {
                if (k >= items[i].from && k < items[i].to) {
                    pos = i;
                    break;
                }
            }
            auto& item = items[pos];
            if (item.repeat > 0) {
                // repeat (remove) prefixes
                k %= item.from;
            } else {
                // remove prefix
                k -= item.from;
                // index based on current range
                return item.value.substr(k, 1);
            }
        }
        // not reachable
        abort();
    }
};