Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 가장 긴 해피(Happy) 문자열 알고리즘

문제 개요

문자열에 'aaa', 'bbb', 'ccc'와 같은 부분 문자열이 하나도 포함되어 있지 않다면, 그 문자열을 해피(happy) 문자열이라고 부릅니다. 세 정수 a, b, c가 주어졌을 때, 다음 조건을 모두 만족하는 문자열 s를 반환하는 것이 이번 문제의 목표입니다.

  • s는 해피 문자열이면서 가능한 한 가장 길어야 합니다.
  • s에는 문자 'a'가 최대 a번, 'b'가 최대 b번, 'c'가 최대 c번까지만 등장할 수 있습니다.
  • s는 오직 'a', 'b', 'c' 세 글자로만 구성되어야 합니다.

조건을 만족하는 문자열을 만들 수 없다면 빈 문자열을 반환하면 됩니다. 예를 들어 a = 1, b = 1, c = 7이 주어지면 "ccaccbcc"와 같은 결과를 얻을 수 있습니다.

접근 방법: 그리디 + 우선순위 큐

이 문제는 그리디(Greedy) 기법과 우선순위 큐(Priority Queue)를 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 매 단계마다 남아 있는 개수가 가장 많은 문자를 우선적으로 배치하되, 같은 문자가 3번 연속으로 이어지지 않도록 제어하는 것입니다.

알고리즘 단계

  1. 문자(a), 남은 개수(cnt), 인덱스(idx)를 함께 저장하는 데이터 구조를 정의합니다.
  2. cnt 값을 기준으로 정렬되는 우선순위 큐 pq를 선언합니다.
  3. a가 0이 아니면 Data('a', a, 0)를 pq에 삽입합니다. 마찬가지로 b, c도 각각 0이 아니면 큐에 넣습니다.
  4. idx := 1, ret := 빈 문자열로 초기화합니다.
  5. 무한 루프를 돌며 다음 과정을 반복합니다.
    • pq에서 최상단(top) 요소를 꺼내 temp에 저장합니다.
    • ret이 비어 있지 않고 ret의 마지막 문자가 temp.a와 같다면, 같은 문자가 3번 연속 배치될 위험이 있는 상황입니다. 이때 pq가 비어 있으면 루프를 종료하고, 그렇지 않으면 두 번째로 많은 문자를 꺼내 대신 사용한 뒤 원래 문자를 다시 큐에 넣습니다.
    • val := 0으로 초기화한 뒤, pq가 비어 있지 않고 (temp.cnt − pq.top().cnt) < 2라면 val := 1로 설정합니다. 그렇지 않으면 val := min(temp.cnt, 2)로 설정합니다. 즉, 다른 문자가 곧 이어질 예정이라면 1개만 붙이고, 여유가 있다면 최대 2개까지 붙일 수 있습니다.
    • ret 뒤에 temp.a를 val개만큼 이어 붙이고, temp.cnt에서 val을 차감합니다.
    • pq가 비어 있으면 루프를 종료합니다.
    • temp.idx := idx로 갱신하고, temp.cnt가 0보다 크면 pq에 다시 삽입합니다.
    • idx를 1 증가시킵니다.
  6. 최종적으로 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
struct Data{
    char a;
    int cnt;
    int idx ;
    Data(char c, int x, int k){
        a = c;
        cnt = x;
        idx = k;
    }
};
struct Cmp{
    bool operator()(Data& a, Data& b) {
        return !(a.cnt>b.cnt);
    }
};
class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<Data, vector<Data>, Cmp> pq;
        if (a)
            pq.push(Data('a', a, 0));
        if (b)
            pq.push(Data('b', b, 0));
        if (c)
            pq.push(Data('c', c, 0));
        int idx = 1;
        string ret = "";
        while (true) {
            Data temp = pq.top();
            pq.pop();
            if (ret.size() && ret.back() == temp.a) {
                if (pq.empty())
                    break;
                Data x = temp;
                temp = pq.top();
                pq.pop();
                pq.push(x);
            }
            int val = 0;
            if (!pq.empty() && temp.cnt - pq.top().cnt < 2) {
                val = 1;
            }
            else
                val = min(temp.cnt, 2);
            ret += string(val, temp.a);
            temp.cnt -= val;
            if (pq.empty())
                break;
            temp.idx = idx;
            if (temp.cnt > 0)
                pq.push(temp);
            idx++;
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.longestDiverseString(1,1,7));
}

실행 결과

입력:

1,1,7

출력:

ccbccacc

문제에서 요구하는 것은 특정 하나의 정답이 아니라 조건을 만족하는 임의의 유효한 문자열이므로, 실행 환경에 따라 "ccaccbcc"처럼 길이가 같은 다른 유효한 결과가 출력될 수도 있습니다. 어떤 경우든 'aaa', 'bbb', 'ccc'가 부분 문자열로 등장하지 않으며, 각 문자의 사용 개수가 주어진 제한을 초과하지 않는다는 점이 보장됩니다.