문자의 ASCII 값을 기준으로 문자열 정렬

ASCII 값

ASCII(American Standard Code for Information Interchange)는 컴퓨터와 인터넷에서 텍스트 데이터에 대한 가장 일반적인 문자 인코딩 형식입니다. 표준 ASCII 인코딩 데이터에서는 256개의 문자, 숫자 또는 특수 추가 문자와 제어 코드가 고유한 값을 갖습니다.

문제 설명

이제 이 문제에서는 문자의 ASCII 값을 기준으로 오름차순으로 정렬된 문자열을 찾아야 합니다. 여기서 문자열은 사용자가 입력한 값이 됩니다. 이 문제를 어떻게 해결해야 하는지 살펴보겠습니다.

몇 가지 예를 통해 이 문제를 이해해 보겠습니다.

Input - s = "$%7wjk()"

출력 - “$%()7jkw”

설명 - 주어진 문자열의 문자의 ASCII 값은 다음과 같습니다 -

으아아아

따라서 ASCII 코드 값의 오름차순으로 문자열은 "$%()7jkw"가 됩니다

Enter - s = "#m 0f )nk"

출력 - “#)0fkmn”

설명 - 주어진 문자열의 문자의 ASCII 값은 다음과 같습니다 -

으아아아

따라서 ASCII 코드 값의 오름차순으로 문자열은 "#)0fkmn"이 됩니다

문제 설명

문제를 이해하고 해결책을 찾으려고 노력합시다. 우리는 ASCII 테이블에 256개의 문자가 있고 각 문자마다 고유한 값이나 위치가 있다는 것을 알고 있습니다. 따라서 우리의 기본 목표는 그에 따라 문자를 정렬하는 것입니다. 목표를 달성하는 데 사용할 수 있는 외부 기능을 사용하여 내장된 정렬 기능을 사용할 수 있습니다. 또 다른 접근 방식은 빈도 벡터를 만들고 해당 배열에 각 문자의 빈도를 저장하는 것입니다. 이 주파수 벡터와 ASCII 값을 사용하여 새 문자열을 얻을 수 있습니다.

해결책 1 주파수 벡터를 사용하세요

알고리즘

• ASCII 테이블의 총 문자 수가 256이므로 크기가 256인 주파수 벡터를 만들고 전체 벡터를 0으로 시작합니다.

• 루프를 실행하여 주어진 문자열의 각 문자의 빈도를 저장하세요

• 이제 처음에는 비어 있는 출력 문자열을 정의하세요

• 다른 루프를 실행하여 주파수 벡터를 반복하면 i번째 위치를 타입 캐스팅하여 출력 문자열을 얻을 수 있습니다.

출력 문자열을 최종 결과로 반환
예

다음은 위 방법의 C++ 프로그램 구현입니다.

으아아아

출력

으아아아

위 코드의 복잡성

시간 복잡도 - O(n); 여기서 n은 문자열의 크기입니다. 여기서 실제 시간 복잡도는 O(n * 256)이지만, 256은 k와 같은 상수로 간주할 수 있고, O(k * n)은 O(n)으로만 간주하므로 O(n)으로 간주할 수 있습니다. .
공간 복잡도 - O(256); 여기서 차지하는 유일한 추가 공간은 256 크기의 주파수 배열을 위한 공간이기 때문입니다.
해결책 2 내장된 정렬 기능을 활용한 해결방안

알고리즘

ASCII 값에 따라 문자를 정렬하는 정렬 함수에 사용되는 외부 비교 함수를 정의합니다. 즉, int 유형 변환 값이 다른 문자보다 작은 문자를 반환합니다.

• 李> 이제 도우미 함수에 내장된 정렬 기능을 사용하고 추가 매개변수(비교 함수)를 사용하여 순서를 올바르게 가져옵니다.
도우미 함수를 호출하고 최종 문자열 출력을 얻습니다.
예

으아아아

출력

으아아아

위 코드의 복잡성

시간 복잡성: 우리 모두 알고 있듯이 내장 정렬 기능은 코드를 실행하는 데 O(n * log(n)) 시간이 걸립니다. 이 방법에서는 해당 기능을 기반으로 문자를 정렬하는 추가 비교 기능을 사용하여 내장된 정렬 기능을 사용하고 있습니다.
공간 복잡성: O(1); 위 코드에서는 일부 데이터 구조에 변수를 저장하지 않습니다.
결론

이 글에서는 문자의 ASCII 값을 기준으로 오름차순으로 정렬된 문자열을 찾습니다. 우리는 두 가지 방법으로 이 문제를 해결할 수 있습니다. 먼저 크기 256(ASCII 테이블의 문자 수와 동일)의 빈도 벡터를 만들고 각 문자의 모든 빈도를 저장한 다음 뒤에서 반복하여 원하는 문자열을 얻을 수 있습니다. 또 다른 방법은 정렬 함수에 전달된 추가 매개변수의 도움으로 내장 정렬 함수를 사용하는 것입니다.

위 내용은 문자의 ASCII 값을 기준으로 문자열 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!