[LeetCode] 1255. Maximum Score Words Formed by Letters

https://leetcode.com/problems/maximum-score-words-formed-by-letters/description/

leetcode - Maximum Score Words Formed by Letters

문제 유형 : 재귀, 백트래킹, dfs, 문자열 처리

문제 난이도 : Hard

 

문제

Given a list of words, list of  single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

 

문자열 배열 words배열이 주어진다. 중복 가능한 단일 문자 배열 letters가 있다. score배열에는 각 글자의 점수가 표기되어있다.

letters에 주어진 문자들로 words의 단어를 만들면, 사용한 글자에 따라서 점수를 얻는다.

(단어 words[i]는 한 번씩만 만들 수 있다.)

 

최대 점수를 반환하시오.

 

풀이

백트래킹으로 쉽게 풀 수 있다.

Letters를 한 번 읽어서 몇 번째 글자가 몇 개 남았는지 저장하는 배열을 하나 만든다. letter_count라고 하겠다.

 

solve(words, score, letter_count, idx, sum)을 재귀적으로 돌면서 아래 동작을 한다: 여기서 idx는 idx번 단어부터 단어를 고르겠다는 뜻이다.

1. ans 업데이트( ans = max(ans, sum))

2. 만약 idx가 벗어났다면, 중지.

3. for문으로 i = idx부터 해서 n까지(n = 단어의 수) 다음을 행한다:

    letter_count의 사본 만들기(백트래킹 위해)

    현재 letter_count로 체크 가능한지 확인한다.(이 과정에서 얻게 될 점수도 같이 계산하고, 사본을 만들어놨으니, letter_count에 직접 개수를 변경해본다.)

    넣을 수 있다면, solve(words, score, letter_count, i, sum + x) (x는 이번에 얻게 된 점수)를 실행한다.

    

    solve가 끝나거나, solve를 실행하지 않건, 즉 백트래킹을 위해 다시 사본을 letter_count에 할당한다.

 

마지막으로, ans를 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    int ans, n;
public:
    int check(vector<string>& words, vector<int>& score, vector<int>& letter_count, int idx) {
        int x = 0;
        for(char ch : words[idx]) {
            int index = ch - 'a';
            if(letter_count[index] <= 0) {
                return -1;
            }
            letter_count[index]--;
            x += score[index];
        }
        return x;
    }
    void solve(vector<string>& words, vector<int>& score, vector<int>& letter_count, int idx, int sum) {
        ans = max(ans, sum);
        if(idx >= n) return;

        for(int i = idx; i < n; i++) {
            vector<int> copy = letter_count;
            int x;
            if((x = check(words, score, letter_count, i)) != -1) {
                solve(words, score, letter_count, i+1, sum + x);
            }
            letter_count = copy;
        }
    }

    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        n = words.size();
        ans = 0;
        vector<int> letter_count(26, 0);

        for(char letter : letters) {
            letter_count[letter - 'a']++;
        }

        for(int i = 0; i < words.size(); i++) {
            solve(words, score, letter_count, i, 0);
        }

        return ans;
    }
};