[LeetCode] 1405. Longest Happy String

https://leetcode.com/problems/longest-happy-string/description/?envType=daily-question&envId=2024-10-16

leetcode - Longest Happy String

문제 유형: 우선순위 큐, 그리디

문제 난이도: Medium

 

문제

A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

 

아래의 조건을 만족하면, 행복한 문자열입니다.

s는 'a', 'b', 그리고 'c'로만 이루어져 있습니다.

s는 'aaa', 'bbb', 'ccc'를 부분문자열로 가지지 않습니다.

s는 최대 a번 'a'를 가집니다.

s는 최대 b번 'b'를 가집니다.

s는 최대 c번 'c'를 가집니다.

 

정수 a, b, c가 주어집니다. 최대한 긴 happy string을 만드시오.

길이가 긴게 여러 개가 있다면, 빈 문자열을 반환하시오.

 

풀이

처음에는 dp[a][b][c]를 놓고 dp + 재귀로 풀려고 했는데, 이는 TLE가 나왔다. 

 

사실, 그리디한 방법으로 풀 수 있었다.

최대 힙의 우선순위 큐를 만들어서, {문자, 개수}의 형태로 저장하고 뒤의 개수를 기준으로 최대 힙을 만들면 된다.

last 변수로 마지막에 나온 문자를 관리하고, streak으로 그 마지막  문자가 몇 번 반복되는지 관리할 수 있다.

 

우선순위 큐에 요소가 있는 동안, 다음을 반복한다:

  이전 스트릭의 문자와 같고, 그 스트릭이 2까지 반복되었다면, 현재 최대 힙의 top을 쓸 수 없다.

  대신, 한번 더 pop해와서 두 번째로 많은 문자를 하나 꺼내서 문자열에 추가한다. 하나만 꺼내도 된다.

  최대한 연장하기 위해서는, 적은 문자는 적게 쓰는 것이 좋다.

  이전 스트릭의 문자를 그 문자로 바꾼다.

 

  그게 아니라면, 현재 최대 힙의 top을 쓸 수 있다.

  문자열에 현재 문자를 하나 추가하고, 이전 스트릭의 문자를 현재 top으로 하고, 스트릭을 1 높인다.

  그러고 업데이트해서 다시 큐에 넣는다.

 

코드

C++

struct comp {
    bool operator()(const pair<char, int> &a, const pair<char, int> &b) {
        return a.second < b.second;
    }
};

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<pair<char, int>, vector<pair<char, int>>, comp> pq; // {char, count}
        if (a > 0) pq.push({'a', a});
        if (b > 0) pq.push({'b', b});
        if (c > 0) pq.push({'c', c});

        string str = "";
        char last = '\0';
        int streak = 0;

        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            
            if (top.first == last && streak == 2) {
                if (pq.empty()) break;

                auto secondary = pq.top();
                pq.pop();

                str += secondary.first;
                last = secondary.first;
                streak = 1;

                if (--secondary.second > 0) pq.push(secondary);
                
                pq.push(top);
            } else {
                str += top.first;
                if (top.first == last) {
                    streak++;
                } else {
                    streak = 1;
                    last = top.first;
                }
                if (--top.second > 0) pq.push(top);
            }
        }

        return str;
    }
};