3264. 2182. Construct String With Repeat Limit

문제 링크


내 코드

19ms, 27.74MB

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        int DAT[26]{};
        for(char c : s) {
            DAT[c - 'a']++;
        }

        string answer{};
        for(int i{25};i>=0;) {
            if(DAT[i]) {
                for(int j{}, e{min(DAT[i], repeatLimit)};j<e;++j) {
                    answer.push_back(i + 'a');
                    DAT[i]--;
                }

                if(DAT[i]) {
                    // another character
                    bool chk{};
                    for(int j = i -1;j>=0;--j) {
                        if(DAT[j]) {
                            answer.push_back(j + 'a');
                            DAT[j]--;
                            chk = true;
                            break;
                        }
                    }
                    if(!chk) return answer;
                }
                // 
            }
            else {
                --i;
            }
        }
        return answer;
    }
};

Solution

Approach 1: Greedy Character Frequency Distribution

  • 9ms, 28.12MB
  • Complexity
    • Let NN be the length of s and KK be the number of unique characters in s.
    • Time Complexity: O(N⋅K)O(N \cdot K)
    • Space Complexity: O(K)O(K)
class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        vector<int> freq(26, 0);
        for (char ch : s) {
            freq[ch - 'a']++;
        }

        string result;
        int currentCharIndex = 25;  // Start from the largest character
        while (currentCharIndex >= 0) {
            if (freq[currentCharIndex] == 0) {
                currentCharIndex--;
                continue;
            }

            int use = min(freq[currentCharIndex], repeatLimit);
            result.append(use, 'a' + currentCharIndex);
            freq[currentCharIndex] -= use;

            if (freq[currentCharIndex] >
                0) {  // Need to add a smaller character
                int smallerCharIndex = currentCharIndex - 1;
                while (smallerCharIndex >= 0 && freq[smallerCharIndex] == 0) {
                    smallerCharIndex--;
                }
                if (smallerCharIndex < 0) {
                    break;
                }
                result.push_back('a' + smallerCharIndex);
                freq[smallerCharIndex]--;
            }
        }

        return result;
    }
};

GPT

아래 코드는 문자열 s에서 각 문자가 몇 개 등장하는지를 센 뒤, 가장 큰(사전순으로 뒤에 오는) 문자부터 repeatLimit만큼 연속해서 넣되, 더 넣을 문자가 남아 있으면 연속을 끊기 위해 바로 이전(더 작은) 문자를 하나만 삽입하고 다시 반복하는 방식으로 최종 문자열을 만드는 로직입니다.

문제 상황 가정

  • 문자열 s가 주어지며, 여기에 등장하는 문자들을 반복 제한(repeatLimit)까지 연속으로 사용할 수 있는 새로운 문자열을 만들어야 합니다.
    • 예: s = "cczaz", repeatLimit = 2
      • 알파벳 빈도 수:
        • c: 2
        • z: 2
        • a: 1
      • 가장 큰 문자(‘z’)부터 시작해서 최대 2개까지 연속해서 배치할 수 있습니다. 연속이 repeatLimit에 도달한 후에도 해당 문자를 더 쓸 수 있다면, 그 사이에 더 작은 문자를 끼워 넣어 “연속 사용”을 끊습니다.

코드 해설

string repeatLimitedString(string s, int repeatLimit) {
    vector<int> freq(26, 0);
    for (char ch : s) {
        freq[ch - 'a']++;
    }

    string result;
    int currentCharIndex = 25;  // Start from the largest character
    while (currentCharIndex >= 0) {
        if (freq[currentCharIndex] == 0) {
            currentCharIndex--;
            continue;
        }

        int use = min(freq[currentCharIndex], repeatLimit);
        result.append(use, 'a' + currentCharIndex);
        freq[currentCharIndex] -= use;

        if (freq[currentCharIndex] > 0) {
            // 아직 해당 문자를 더 넣을 수 있는데,
            // repeatLimit 때문에 연속으로 넣을 수 없으므로
            // 그보다 작은 문자를 하나 넣어서 연속을 끊어준다.
            int smallerCharIndex = currentCharIndex - 1;
            while (smallerCharIndex >= 0 && freq[smallerCharIndex] == 0) {
                smallerCharIndex--;
            }
            if (smallerCharIndex < 0) {
                // 더 이상 작은 문자가 없다면 종료
                break;
            }
            result.push_back('a' + smallerCharIndex);
            freq[smallerCharIndex]--;
        }
    }

    return result;
}

1. 알파벳 빈도 수 계산

vector<int> freq(26, 0);
for (char ch : s) {
    freq[ch - 'a']++;
}
  • freq 배열에 s에서 등장하는 각 문자의 개수를 저장합니다.
    • 예: s = "cczaz"라면
      • freq['c' - 'a'] = 2, freq['z' - 'a'] = 2, freq['a' - 'a'] = 1 등등.

2. 가장 큰 문자부터 검사

int currentCharIndex = 25;  // 알파벳 'z'에 해당 ('a'=0, 'z'=25)
while (currentCharIndex >= 0) {
    if (freq[currentCharIndex] == 0) {
        currentCharIndex--;
        continue;
    }
    ...
}
  • 알파벳이 0번 인덱스(‘a’)부터 25번 인덱스(‘z’)까지 있으므로, currentCharIndex = 25부터 시작해 빈도 수가 있는 문자를 찾습니다.
  • 해당 문자의 빈도(freq[currentCharIndex])가 0이 아니라면, 그 문자를 사용할 차례입니다.

3. 현재 문자 사용 (최대 repeatLimit만큼)

int use = min(freq[currentCharIndex], repeatLimit);
result.append(use, 'a' + currentCharIndex);
freq[currentCharIndex] -= use;
  • 사용할 수 있는 개수와 repeatLimit 중 더 작은 값(use)만큼을 result 문자열에 연속으로 붙입니다.
  • 예: freq[currentCharIndex] = 5, repeatLimit = 2라면, use = 2
    • result에 해당 문자를 2개 붙이고, 나머지 freq[currentCharIndex]에서 2를 뺍니다(5 → 3).

4. 연속을 끊을 필요가 있다면, 더 작은 문자를 하나 삽입

if (freq[currentCharIndex] > 0) { 
    // 더 쓸 수 있는 문자가 아직 남았음
    // 하지만 repeatLimit 때문에 연속 사용 불가

    int smallerCharIndex = currentCharIndex - 1;
    while (smallerCharIndex >= 0 && freq[smallerCharIndex] == 0) {
        smallerCharIndex--;
    }
    if (smallerCharIndex < 0) {
        // 더 이상 작은 문자가 없으면 반복 중단
        break;
    }
    result.push_back('a' + smallerCharIndex);
    freq[smallerCharIndex]--;
}
  • 현재 문자(currentCharIndex)를 아직 더 쓸 수 있는데(freq[currentCharIndex] > 0), repeatLimit 한도만큼 이미 연속해서 넣은 상태라면, 연속을 끊어줄 다른 문자를 하나 끼워넣어야 합니다.
  • “작은 문자”란, currentCharIndex보다 인덱스가 낮은 알파벳입니다. currentCharIndex - 1부터 시작하여 빈도 수(freq[smallerCharIndex])가 0이 아닌 알파벳을 찾습니다.
  • 만약 작은 문자가 존재하지 않으면(smallerCharIndex < 0), 더 이상 결과 문자열을 만들 방법이 없으므로 반복을 중단합니다.
  • 작은 문자를 하나 넣어준 뒤, 그 문자의 빈도도 1 감소시킵니다.

5. 반복 종료

  • 위 과정(3번, 4번)을 현재 문자를 사용할 수 있을 때까지 (또는 작은 문자가 없어서 중단될 때까지) 계속합니다.
  • 모든 알파벳에 대해 검사한 뒤, 최종적으로 result를 반환합니다.

동작 예시

예를 들어,

  • 입력: s = "cczaz", repeatLimit = 2
  • 알파벳 빈도:
    • 'z' - 'a' = 25: 2
    • 'c' - 'a' = 2
    • 'a' - 'a' = 1
  • currentCharIndex = 25('z') → 빈도 2 있으므로 use = min(2, 2) = 2
    • result = "zz", freq[z] = 0 (2 - 2)
    • freq[z] == 0 → 더 쓸 ‘z’ 없으니 작은 문자 끼울 필요 X
  • 다음으로 currentCharIndex = 24부터 0까지 찾아가며, 24~3에는 빈도가 없으니 pass, currentCharIndex = 2('c')에서 빈도 2
    • use = min(2, 2) = 2 → result = "zzcc", freq[c] = 0
    • 남은 빈도 0이므로 작은 문자 삽입 X
  • currentCharIndex = 1~0 → 'a'에서 빈도 1
    • use = min(1, 2) = 1 → result = "zzcca", freq[a] = 0
    • 더 이상 freq[a] > 0가 아니므로 끝
  • 최종 결과: "zzcca"

결론

  • 핵심 아이디어: 가장 큰 문자부터 repeatLimit만큼 연속해서 붙이고, 남은 빈도가 있으면 작은 문자를 하나 끼워 넣어 연속 제한을 회피한 뒤 다시 같은 문자를 이어 붙이는 식으로 진행합니다.
  • 최종적으로, 사전순으로 가장 내림차순에 가까우면서(가장 큰 문자를 최대한 많이 앞쪽에 배치), 연속 제한도 준수하는 문자열을 얻을 수 있습니다.

Approach 2: Heap-Optimized Greedy Character Frequency Distribution

  • 63ms, 28.49MB
  • Complexity
    • Let NN be the length of s and KK be the number of unique characters in s.
    • Time Complexity: O(N⋅log⁡K)O(N \cdot \log K)
    • Space Complexity: O(K)O(K)
class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        unordered_map<char, int> freq;
        for (char ch : s) {
            freq[ch]++;
        }

        priority_queue<char> maxHeap;
        for (auto& [ch, count] : freq) {
            maxHeap.push(ch);
        }

        string result;

        while (!maxHeap.empty()) {
            char ch = maxHeap.top();
            maxHeap.pop();
            int count = freq[ch];

            int use = min(count, repeatLimit);
            result.append(use, ch);

            freq[ch] -= use;

            if (freq[ch] > 0 && !maxHeap.empty()) {
                char nextCh = maxHeap.top();
                maxHeap.pop();

                result.push_back(nextCh);
                freq[nextCh]--;

                if (freq[nextCh] > 0) {
                    maxHeap.push(nextCh);
                }

                maxHeap.push(ch);
            }
        }

        return result;
    }
};

GPT

아래 코드는 우선순위 큐(최대 힙) 를 사용해, 문자열에서 가장 큰 문자를 최대 연속 제한(repeatLimit)만큼 붙여나가되, 그 연속 제한을 넘어가면 중간에 다른(더 작은) 문자를 하나 끼워넣으며 결과를 생성하는 방식입니다. 구체적인 과정을 단계별로 살펴봅시다.

1. 문자 빈도 수 계산

unordered_map<char, int> freq;
for (char ch : s) {
    freq[ch]++;
}
  • 문자열 s에 등장하는 각 문자 ch의 빈도(등장 횟수)를 freq[ch]에 저장합니다.

2. 최대 힙(우선순위 큐) 구성

priority_queue<char> maxHeap;
for (auto& [ch, count] : freq) {
    maxHeap.push(ch);
}
  • freq에 등록된 모든 문자 ch를 최대 힙인 maxHeap에 넣습니다.
  • 최대 힙: 가장 큰 문자가 top()에서 뽑히도록 구성됩니다.

3. 결과 문자열 생성

string result;

while (!maxHeap.empty()) {
    char ch = maxHeap.top();
    maxHeap.pop();

    int count = freq[ch];
    int use = min(count, repeatLimit);
    result.append(use, ch);
    freq[ch] -= use;

    // 아직 더 쓸 수 있는 ch가 남아있고, 힙에 다른 문자가 있다면
    // 연속 제한을 끊어주기 위해 중간에 다른 문자를 하나 끼운다.
    if (freq[ch] > 0 && !maxHeap.empty()) {
        char nextCh = maxHeap.top();
        maxHeap.pop();

        // 하나 끼워넣어서 연속 제한을 끊어준다
        result.push_back(nextCh);
        freq[nextCh]--;

        // nextCh 문자 개수가 아직 남아 있다면 다시 힙에 넣는다
        if (freq[nextCh] > 0) {
            maxHeap.push(nextCh);
        }

        // 아직 남아있는 ch도 다시 힙에 넣어, 차례가 되었을 때 이어서 사용할 수 있게 한다
        maxHeap.push(ch);
    }
}

  1. 가장 큰 문자 꺼내기

    • ch = maxHeap.top()으로 최대 힙에서 가장 큰 문자를 가져옵니다.
    • maxHeap.pop()으로 해당 문자를 힙에서 제거합니다.

  2. repeatLimit만큼(또는 남은 빈도만큼) 결과에 붙이기

    • count = freq[ch]가 실제로 남은 횟수이며, use = min(count, repeatLimit)는 연속 제한에 의해 한 번에 사용할 수 있는 최대 횟수입니다.
    • result.append(use, ch)로 use만큼 ch 문자를 이어붙이고, freq[ch] -= use로 소모된 만큼 빈도 수를 줄입니다.

  3. 연속 제한을 끊을 필요가 있는 경우

    • freq[ch] > 0인 경우, 아직 ch를 더 붙일 수 있습니다.
    • 하지만 이미 repeatLimit만큼 연속해서 붙였으므로, 그대로 붙이면 제한을 초과하게 됩니다.
    • 그래서 “연속을 끊을” 다른 문자를 하나 끼워 넣어야 합니다.
      • if (freq[ch] > 0 && !maxHeap.empty()) 조건을 만족하면, 힙에서 가장 큰 나머지 문자(nextCh)를 하나 꺼내서 result.push_back(nextCh)로 넣고, 그 빈도도 1만큼 줄입니다.
      • nextCh 문자가 여전히 남아 있으면(freq[nextCh] > 0), 다시 힙에 넣어줍니다.
      • 아직 남아 있는 ch도 다시 힙에 넣어, 다음 반복 때 연속 없이 다시 쓸 수 있도록 합니다.

4. 결과 문자열 반환

  • 더 이상 힙이 비어있지 않을 때까지(또는 ch가 없을 때까지) 위 과정을 반복하면 result가 완성됩니다.
  • 마지막에 result를 반환합니다.

동작 예시

예를 들어,

  • s = "cczaz", repeatLimit = 2인 경우:
    1. 문자별 빈도:
      • z: 2, c: 2, a: 1
    2. 최대 힙에는 z, c, a가 들어 있고, 가장 먼저 z가 나온다.
      • use = min(2, 2) = 2 → result = "zz", freq[z] = 0
      • freq[z] = 0이므로, z를 더 끼울 필요 X → 다음 문자를 가져옴
    3. 그 다음으로 c(freq=2) 최대 힙에서 꺼내서
      • result = "zzcc", freq[c] = 0
    4. 남은 문자는 a(freq=1), → result = "zzcca"
    5. 최종 결과: "zzcca"

이처럼, 가장 큰 문자부터 최대 repeatLimit까지 연속해서 붙이되, 남은 빈도가 있다면 중간에 다른 문자를 하나 끼워 넣어 연속 제한을 지키도록 설계된 코드입니다.