인접하지 않은 문자를 제거하여 이진 문자열을 내림차순으로 정렬할 수 있는지 확인

이 문제에서는 인접하지 않은 요소만 제거하여 주어진 바이너리 문자열을 내림차순으로 정렬해야 합니다.

이 문제를 해결하려면 이진 문자열에서 1 앞에 오는 0을 모두 제거해야 합니다. 문자열 어디에서나 두 개의 연속된 0과 두 개의 연속된 1을 발견하면 문자열을 내림차순으로 정렬할 수 없다는 의미입니다. 그렇지 않으면 각 상황을 분류할 수 있습니다.

문제 설명 - N과 동일한 길이의 이진 문자열 str이 제공됩니다. 문자열에서 인접하지 않은 여러 문자를 제거하여 주어진 문자열을 내림차순으로 정렬할 수 있는지 확인해야 합니다. 주어진 문자열. 문자열을 내림차순으로 정렬할 수 있으면 "yes"를 인쇄하고, 그렇지 않으면 "no"를 인쇄합니다.

예

으아아아 으아아아

지침

두 번째와 네 번째 위치에서 "0"을 제거하면 문자열을 내림차순으로 정렬할 수 있습니다.

으아아아 으아아아

지침

문자열이 정렬됩니다.

으아아아 으아아아

지침

여기서 문자열을 정렬하려면 1, 3, 4, 5번째 위치의 0을 제거해야 하는데 인접한 0은 제거할 수 없습니다. 또는 모든 "1"을 제거하여 문자열을 정렬할 수 있지만 두 개의 "1"이 인접해 있기 때문에 이 역시 불가능합니다.

방법 1

이 방법에서는 끝부터 시작하여 문자열을 반복합니다. 두 개의 연속된 "1"을 찾으면 루프가 중단됩니다. 그런 다음 문자열에 두 개의 연속된 "0"이 포함되어 있는지 확인합니다. 그렇다면 false를 반환합니다. 그렇지 않으면 true를 반환합니다.

알고리즘

• 1단계 - for 루프를 사용하여 'len – 2'에서 0까지 문자열 반복을 시작합니다. 여기서 'len'은 주어진 이진 문자열의 길이입니다.

• 2단계 - str[i]와 str[i+1]이 모두 "1"이면 "break" 키워드를 사용하여 루프를 종료합니다.

• 3단계 - 이제 i번째 인덱스부터 문자열 순회를 시작합니다.

• 4단계 - str[j]와 str[j+1]이 모두 '0'이면 0을 반환합니다. 루프가 성공적으로 종료되면 1을 반환합니다. p>

• 5단계 - isSortPossible() 함수의 반환 값을 기반으로 드라이버 코드에 "YES" 또는 "NO"를 인쇄합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N), 문자열을 반복할 때.

공간 복잡성 - O(1)

방법 2

이 방법에서는 첫 번째 방법과 동일한 논리를 사용하지만 더 읽기 쉽게 코드를 최적화했습니다. 여기서는 두 개의 개별 루프를 사용하는 대신 단일 루프만 사용하여 두 개의 연속 "0" 다음에 두 개의 연속 "1"을 감지합니다.

알고리즘

• 1단계 - "isTwoZeros" 변수를 정의하고 "false" 값으로 초기화합니다.

• 2단계 - 0번째 인덱스부터 "len – 1"까지 문자열 반복을 시작합니다.

• 3단계 - str[i] 및 str[I + 1]이 "0"이고 "isTwoZeros"가 false인 경우 "isTwoZeros" 값을 true로 변경합니다. 이는 주어진 문자열에 두 개의 연속된 0이 있다는 것을 의미합니다.

• 4단계 - else 부분에서 str[i] 및 str[I + 1]이 '1'이고 'isTwoZeros'가 true이면 함수에서. 이는 두 개의 연속된 0 뒤에 두 개의 연속된 "1"이 표시됨을 의미합니다.

• 5단계 - for 루프의 모든 반복이 종료되면 true를 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N)

공간 복잡성 - O(1)

결론

인접하지 않은 문자만 제거하여 이진 문자열을 내림차순으로 정렬하는 두 가지 방법을 배웠습니다. 두 방법 모두 코드 변경을 최소화하면서 동일한 논리를 사용합니다. 두 번째 접근 방식의 코드는 첫 번째 접근 방식의 코드보다 읽기 쉽습니다.

위 내용은 인접하지 않은 문자를 제거하여 이진 문자열을 내림차순으로 정렬할 수 있는지 확인의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!