문자열이 있다고 가정합니다. 하위 문자열로 'aaa', 'bbb' 또는 'ccc'와 같은 문자열이 없는 경우 해당 문자열을 happy라고 합니다. b, c와 같은 세 개의 정수가 있는 경우 다음 조건을 충족하는 문자열 s를 반환합니다. -
-
s는 행복하고 가장 긴 시간입니다.
-
s는 최대 문자 'a', 최대 b번의 문자 'b', 최대 c번의 문자 'c'를 포함합니다.
-
s는 'a', 'b' 및 'c' 문자만 포함합니다.
해당 문자열이 없으면 빈 문자열을 반환합니다.
따라서 입력이 a =1, b =1, c =7과 같으면 출력은 "ccaccbcc"가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
문자, inx 및 cnt가 있는 하나의 데이터 구조 정의
-
하나의 우선순위 큐 pq를 정의하면 데이터의 cnt 값을 사용하여 우선순위가 지정됩니다.
-
a가 0이 아닌 경우 -
-
pq에 새 데이터('a', a, 0) 삽입
-
-
b가 0이 아닌 경우 -
-
pq에 새 데이터('b', b, 0) 삽입
-
-
c가 0이 아니면 -
-
pq에 새 데이터('c', c, 0) 삽입
-
-
아이디:=1
-
ret :=빈 문자열
-
true가 0이 아닌 동안 수행 -
-
temp :=pq의 최상위 요소
-
pq에서 요소 삭제
-
ret의 크기가 0이 아니고 ret의 마지막 요소가 temp.a와 같으면 -
-
pq가 비어 있으면 -
-
루프에서 나오세요
-
-
x :=온도
-
temp :=pq의 최상위 요소
-
pq에서 요소 삭제
-
pq에 x 삽입
-
-
값 :=0
-
pq가 비어 있지 않은 경우 temp의 cnt - pq의 첫 번째 요소의 cnt <2이면 -
-
값 :=1
-
-
그렇지 않으면
-
val :=온도의 cnt와 2의 최소값
-
-
ret :=ret val에 있는 temp.a의 인덱스에서 val을 끝으로 연결
-
temp.cnt :=temp.cnt - val
-
pq가 비어 있으면 -
-
루프에서 나오세요
-
-
temp.idx :=idx
-
temp.cnt> 0이면 -
-
pq에 temp 삽입
-
-
(idx를 1씩 증가)
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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