주어진 두 문자열이 서로 순열이 되도록 필요한 작업 수를 최소화합니다.

이 기사에서는 주어진 두 문자열을 서로 정렬하는 데 필요한 주어진 연산 수를 최소화하는 방법에 대해 논의합니다. 우리는 단계별 접근 방식을 따르고 C++ 코드 구현을 제공할 것입니다. 또한 문제와 해결 방법을 이해하는 데 도움이 되는 샘플 테스트 사례도 제공합니다.

문제 설명

두 개의 문자열 s1과 s2가 주어지면 s1과 s2를 서로 정렬하는 데 필요한 최소 연산 수를 찾아야 합니다. s1의 두 문자를 바꾸거나 s2의 두 문자를 바꾸는 두 가지 작업을 수행할 수 있습니다.

방법론 및 구현

이 문제를 해결하려면 두 문자열에 존재하지 않는 문자 수, 즉 두 문자열에 문자가 나타나는 빈도의 차이를 계산해야 합니다. 두 문자열을 서로 정렬하는 데 필요한 최소 교환 횟수는 이 수의 절반과 같습니다. 두 문자열의 문자를 교환하여 동일하게 만들 수 있기 때문입니다.

먼저 두 배열을 사용하여 두 문자열의 문자 빈도를 계산합니다. 그런 다음 두 배열을 반복하고 문자 빈도 간의 절대 차이를 변수에 추가합니다. 이 변수는 두 문자열 모두에 존재하지 않는 문자 수를 저장합니다.

개수를 계산한 후 두 문자열이 서로 순열되는 데 필요한 최소 스왑 수로 그 절반을 반환합니다.

예

다음은 위 메소드의 C++ 코드 구현입니다. -

으아악

출력

으아악

예제 테스트 사례

이 테스트 사례에 대한 예제 문자열 "hello" 및 "world"를 고려해 보겠습니다.

두 줄의 주파수 배열은 다음과 같습니다 -

으아악

문자 "l"은 s1에서는 빈도 2로 나타나지만 s2에서는 1만 나타나는 반면 문자 "r"은 s2에서는 빈도 1로 나타나지만 s1에는 없습니다. 따라서 두 문자열 모두에 존재하지 않는 문자 수는 3입니다.

따라서 두 문자열이 서로 치환되는 데 필요한 최소 스왑 횟수는 1입니다. s1의 "l"을 s2의 "r"로 바꾸어 서로 순열인 "herlo"와 "wolld" 문자열을 얻을 수 있습니다.

결론

이 기사에서는 주어진 두 문자열을 서로 정렬하는 데 필요한 주어진 작업 수를 최소화하는 방법에 대해 논의했습니다. 우리는 단계별 접근 방식을 따르고 C++ 코드 구현을 제공했습니다. 또한 문제와 해결 방법을 이해하는 데 도움이 되는 샘플 테스트 사례도 제공합니다. 문제는 O(n) 시간 복잡도와 O(1) 공간 복잡도로 풀 수 있습니다.

위 내용은 주어진 두 문자열이 서로 순열이 되도록 필요한 작업 수를 최소화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!