주어진 문자를 사용하여 최소 2개의 서로 다른 문자를 포함하는 길이가 3인 문자열의 개수를 셉니다.

세 개의 서로 다른 문자 "A", "B" 및 "C"의 발생 빈도를 나타내는 세 개의 정수 "a", "b" 및 "c"를 알려주세요. 우리는 이들 문자를 이용하여 형성할 수 있는 서로 다른 문자열의 수를 찾아야 하며, 형성된 문자열에는 최소한 두 개의 서로 다른 문자가 존재해야 합니다. 우리는 이 문제를 해결하는 두 가지 방법을 살펴보겠습니다. 하나는 순진한 방법이고 다른 하나는 수학적 방법입니다.

예

으아아아 으아아아

지침

"ABC", "ABC", "ACC" 세 개의 문자열을 만들 수 있습니다. 이 문자열에는 'A'가 3번, 'B'가 2번, 'C'가 4번 사용되는데, 이는 주어진 빈도와 같거나 적은 빈도이며, 모든 문자열에는 최소 2개의 서로 다른 문자가 포함되어 있습니다. p> 으아아아 으아아아

지침

"ACC", "BCC", "BCC" 및 "BCC" 문자열을 만들 수 있습니다. 새 문자열을 생성하는 데 사용할 다른 문자가 없기 때문에 두 개의 "C"를 제외한 모든 주어진 문자를 사용했습니다. 다른 조합을 시도했다면 최종 문자열 수는 더 적었을 것입니다.

순진한 방법

가장 간단한 방법은 주어진 주파수의 가능한 모든 조합을 찾는 것이지만, 문제는 이것이 많은 시간 복잡도를 필요로 하고 극도로 비효율적이라는 것입니다.

가능한 모든 부분 문자열을 생성해야 하는데, 숫자가 크면 컴퓨터가 처리할 수 없을 정도로 많은 시간과 공간이 필요합니다.

수학적 방법

아이디어

이 방법의 기본 아이디어는 문자열에 최소한 두 개의 서로 다른 문자가 필요하므로 항상 가장 빈도가 낮은 문자에 집중하려고 노력한다는 것입니다.

만들 수 있는 최대 문자열 수는 (a+b+c)/3이며, 가능한 수는 최소 2개 이상의 발생 빈도에 따라 달라집니다.

적어도 두 개의 주파수가 x와 y이고 그 합이 (a+b+c)/3보다 크거나 같다고 가정하면 이 값을 답으로 인쇄할 수 있고, 그렇지 않으면 x와 y의 합이 답이 됩니다.

구현

해결책을 찾기 위한 예제와 아이디어를 살펴보았습니다. 이제 코드 구현을 시작해 보겠습니다.

• 먼저 세 개의 정수를 받아 하나의 정수를 반환하는 함수를 만들어 보겠습니다.

• 함수에서는 먼저 모든 정수를 벡터에 저장한 다음 벡터를 정렬하여 최소 빈도 정수를 얻습니다.

• 주어진 모든 요소의 합을 구한 다음 3으로 나누어 만들 수 있는 최대 문자열 수를 구합니다.

• 나중에 가장 큰 문자열의 값과 두 주파수의 합이 가장 작은 값을 비교해 보겠습니다. 합이 더 작으면 최대 문자열을 업데이트하여 최소 두 개의 주파수 요소의 합이 되도록 합니다.

• 마지막으로 가능한 가장 큰 문자열의 값을 반환하고 이를 메인 함수에 인쇄합니다.

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 결과를 얻기 위해 루프나 재귀 호출을 사용하지 않기 때문에 O(1) 또는 상수입니다.

위 코드의 공간 복잡도는 여기서 추가 공간을 사용하지 않기 때문에 O(1)입니다.

결론

이 튜토리얼에서는 최소 2개의 서로 다른 문자가 포함된 주어진 문자를 사용하여 개수가 3인 3개의 길이 문자열을 찾는 프로그램을 구현했습니다. 우리는 간단한 방법을 논의하고 일정한 시간 및 공간 복잡도(예: O(1))를 갖는 수학적 방법을 구현했습니다.

위 내용은 주어진 문자를 사용하여 최소 2개의 서로 다른 문자를 포함하는 길이가 3인 문자열의 개수를 셉니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!