찾다
백엔드 개발PHP 튜토리얼범위 I에서 선택할 수 있는 최대 정수 수

Maximum Number of Integers to Choose From a Range I

2554. 범위 I에서 선택할 수 있는 최대 정수 수

난이도:

주제: 배열, 해시 테이블, 이진 검색, 탐욕, 정렬

금지된 정수 배열과 두 개의 정수 n 및 maxSum이 제공됩니다. 아래 규칙에 따라 몇 가지 정수를 선택합니다.

  • 선택한 정수는 [1, n] 범위에 있어야 합니다.
  • 각 정수는 최대 한 번 선택할 수 있습니다.
  • 선택한 정수는 금지된 배열에 있어서는 안 됩니다.
  • 선택한 정수의 합은 maxSum을 초과할 수 없습니다.

언급된 규칙에 따라 선택할 수 있는 최대 정수 수를 반환합니다.

예 1:

  • 입력: 금지 = [1,6,5], n = 5, maxSum = 6
  • 출력: 2
  • 설명: 정수 2와 4를 선택할 수 있습니다.
    • 2와 4는 [1, 5] 범위에 속하며 둘 다 금지 항목에 나타나지 않았으며 합은 6으로 maxSum을 초과하지 않았습니다.

예 2:

  • 입력: 금지 = [1,2,3,4,5,6,7], n = 8, maxSum = 1
  • 출력: 0
  • 설명: 언급된 조건을 따르는 동안에는 정수를 선택할 수 없습니다.

예 3:

  • 입력: 금지 = [11], n = 7, maxSum = 50
  • 출력: 7
  • 설명: 정수 1, 2, 3, 4, 5, 6, 7을 선택할 수 있습니다.
    • [1, 7] 범위에 속하고 모두 금지 항목에 나타나지 않았으며 합은 28로 maxSum을 초과하지 않았습니다.

제약조건:

  • 1 4
  • 1 4
  • 1 9

힌트:

  1. n보다 작은 금지 숫자를 세트로 유지하세요.
  2. 1부터 n까지의 숫자를 반복하여 숫자가 금지되지 않은 경우 사용하세요.
  3. 금지되지 않은 동안 숫자를 계속 추가하고 그 합이 k보다 작습니다.

해결책:

1부터 n까지 숫자를 반복하고 금지된 숫자를 건너뛰고 maxSum에 도달할 때까지 유효한 숫자(금지된 배열에 없는 숫자)를 누계에 계속 추가하는 탐욕적 접근 방식을 사용할 수 있습니다.

다음은 단계별 해결 방법입니다.

단계:

  1. 빠른 조회를 위해 금지된 배열을 집합으로 변환: array_flip()을 사용하면 금지된 배열을 O(1) 평균 시간 복잡도 조회를 위한 집합으로 변환할 수 있습니다.
  2. 1에서 n까지 반복: 각 숫자를 확인하여 금지된 세트에 없고 추가하는 것이 maxSum을 초과하지 않는 경우 합계에 추가하고 개수를 늘립니다.
  3. 다음 숫자를 더하는 것이 maxSum을 초과하면 중지하세요. 목표는 합을 초과하지 않고 선택한 정수의 수를 최대화하는 것이므로 이러한 욕심 많은 접근 방식을 통해 사용 가능한 가장 작은 숫자를 먼저 가져옵니다.

접근하다:

  1. 금지된 번호 제외: 빠른 조회를 위해 금지된 번호를 집합(또는 연관 배열)으로 추적합니다.
  2. 탐욕스러운 선택: 1부터 n까지의 숫자를 오름차순으로 선택하기 시작하세요. 이렇게 하면 선택된 정수의 수를 최대화할 수 있습니다. 숫자를 선택할 때마다 해당 숫자를 합계에 추가하고 숫자가 maxSum을 초과하는지 확인합니다. 그렇다면 중지하세요.
  3. 효율성 고려 사항: 1부터 n까지의 숫자를 반복하고 각 숫자가 금지된 세트에 있는지 확인하므로(일정한 시간에 수행 가능) 접근 방식은 n과 관련하여 선형 시간으로 실행됩니다. 금지 목록의 크기.

이 솔루션을 PHP로 구현해 보겠습니다: 2554. 범위 I에서 선택할 수 있는 최대 정수 수

<?php /**
 * @param Integer[] $banned
 * @param Integer $n
 * @param Integer $maxSum
 * @return Integer
 */
function maxCount($banned, $n, $maxSum) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxCount([1, 6, 5], 5, 6);  // Output: 2
echo "\n";
echo maxCount([1, 2, 3, 4, 5, 6, 7], 8, 1);  // Output: 0
echo "\n";
echo maxCount([11], 7, 50);  // Output: 7
?>

설명:

  1. 금지된 배열을 집합으로 변환:

    array_flip($banned)을 사용하여 금지된 배열에서 세트를 생성합니다. 이를 통해 O(1) 조회를 통해 숫자가 금지되었는지 확인할 수 있습니다.

  2. 1부터 n까지 반복:

    1부터 n까지의 숫자를 반복합니다. 각 번호에 대해:

    • 번호가 금지된 세트에 없는 경우(isset($bannedSet[$i])를 사용하여 확인),
    • 그리고 합계에 숫자를 더하면 maxSum을 초과하지 않는 경우
    • 해당 숫자를 포함하고 합계와 개수를 업데이트합니다.
  3. 카운트 반환:

    루프 후에는 선택한 정수의 수($count)를 반환합니다.

  4. $bannedSet = array_flip($banned);: 빠른 조회를 위해 금지 목록을 세트(연관 배열)로 변환합니다.

  5. for ($i = 1; $i : 1부터 n까지의 모든 정수를 반복합니다.

  6. if (isset($bannedSet[$i])) { 계속; }: 현재 번호가 금지된 세트에 있는지 확인합니다. 그렇다면 건너뛰겠습니다.

  7. if ($sum $i > $maxSum) { break; }: 현재 추가한 숫자가 maxSum을 초과하면 프로세스를 중지합니다.

  8. $sum = $i; $count ;: 숫자가 유효하고 숫자를 더하면 maxSum을 초과하지 않으면 합계에 포함하고 개수를 늘립니다.

시간 복잡도:

  • 금지된 집합(array_flip)의 생성은 O(b)이며, 여기서 b는 금지된 배열의 길이입니다.
  • 루프는 n번 반복되며(1에서 n까지의 숫자에 대해) 금지된 세트를 조회할 때마다 O(1) 시간이 걸립니다. 따라서 루프의 시간복잡도는 O(n)입니다.
  • 따라서 전체 시간 복잡도는 O(n b)이며, 이는 문제 제약 조건을 고려할 때 효율적입니다.

예제 연습:

입력:

  • 입력 1: 금지 = [1, 6, 5], n = 5, maxSum = 6

    • 금지 세트: {1, 5, 6}을 생성합니다.
    • 1부터 5까지 반복합니다.
      • 1개가 차단되었습니다. 건너뛰세요.
      • 2는 금지되지 않습니다. 합계에 추가하세요(합계 = 2, 개수 = 1).
      • 3은 금지되지 않습니다. 합에 추가하세요(합 = 5, 개수 = 2).
      • 4는 금지되지 않지만 합계에 추가하면 maxSum(5 4 = 9)을 초과하므로 건너뜁니다.
    • 결과는 2입니다.
  • 입력 2:banned = [1, 2, 3, 4, 5, 6, 7], n = 8, maxSum = 1

    • 1부터 7까지의 숫자는 모두 금지되어 있어 유효한 숫자를 선택할 수 없습니다.
    • 결과는 0입니다.
  • 입력 3: 금지 = [11], n = 7, maxSum = 50

    • 유일한 금지 숫자는 11부터 7까지의 범위를 벗어난 숫자입니다.
    • 1부터 7까지의 숫자를 모두 선택할 수 있으며 그 합은 28로 maxSum보다 작습니다.
    • 결과는 7입니다.

이 솔루션은 주어진 제약 내에서 문제를 효율적으로 처리합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 범위 I에서 선택할 수 있는 최대 정수 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
PHP에서 인터페이스를 어떻게 생성하고 사용합니까?PHP에서 인터페이스를 어떻게 생성하고 사용합니까?Apr 30, 2025 pm 03:40 PM

이 기사는 PHP의 인터페이스를 생성, 구현 및 사용하는 방법을 설명하여 코드 구성 및 유지 관리에 대한 이점에 중점을 둡니다.

crypt ()와 password_hash ()의 차이점은 무엇입니까?crypt ()와 password_hash ()의 차이점은 무엇입니까?Apr 30, 2025 pm 03:39 PM

이 기사에서는 PHP의 암호 해싱에 대한 Crypt ()와 Password_hash ()의 차이점에 대해 논의하여 최신 웹 애플리케이션에 대한 구현, 보안 및 적합성에 중점을 둡니다.

PHP의 크로스 사이트 스크립팅 (XSS)을 어떻게 방지 할 수 있습니까?PHP의 크로스 사이트 스크립팅 (XSS)을 어떻게 방지 할 수 있습니까?Apr 30, 2025 pm 03:38 PM

기사는 입력 유효성 검사, 출력 인코딩 및 OWASP ESAPI 및 HTML 청정기와 같은 도구를 통해 PHP의 크로스 사이트 스크립팅 (XSS) 방지에 대해 논의합니다.

PHP의 자동로드 란 무엇입니까?PHP의 자동로드 란 무엇입니까?Apr 30, 2025 pm 03:37 PM

PHP의 자동로드는 필요할 때 클래스 파일을 자동으로로드하여 메모리 사용을 줄이고 코드 구성을 향상시켜 성능을 향상시킵니다. 모범 사례에는 PSR-4 사용 및 효과적으로 코드 구성이 포함됩니다.

PHP 스트림이란 무엇입니까?PHP 스트림이란 무엇입니까?Apr 30, 2025 pm 03:36 PM

PHP 스트림은 일관된 API를 통해 파일, 네트워크 소켓 및 압축 형식과 같은 자원의 처리를 통합하여 복잡성을 추상화하고 코드 유연성 및 효율성을 향상시킵니다.

PHP를 사용하여 업로드 할 수있는 파일의 최대 크기는 얼마입니까?PHP를 사용하여 업로드 할 수있는 파일의 최대 크기는 얼마입니까?Apr 30, 2025 pm 03:35 PM

이 기사에서는 PHP의 파일 업로드 크기 관리, 기본 제한 2MB 및 php.ini 설정을 수정하여이를 늘리는 방법에 중점을 둔 파일 업로드 크기 관리에 대해 설명합니다.

PHP의 무효 유형은 무엇입니까?PHP의 무효 유형은 무엇입니까?Apr 30, 2025 pm 03:34 PM

이 기사에서는 PHP 7.1에 도입 된 PHP의 무효 유형에 대해 설명하여 변수 또는 매개 변수가 지정된 유형 또는 널이 될 수 있습니다. 개선 된 가독성, 유형 안전 및 명시 적 의도와 같은 이점을 강조하고 선언하는 방법을 설명합니다.

unset ()와 unlink () 함수의 차이점은 무엇입니까?unset ()와 unlink () 함수의 차이점은 무엇입니까?Apr 30, 2025 pm 03:33 PM

이 기사에서는 Unset ()와 Unlink () 기능의 차이점에 대해 설명합니다. 프로그래밍의 목적 및 사용 사례에 중점을 둡니다. unset ()는 메모리에서 변수를 제거하고 Unlink ()는 파일 시스템에서 파일을 삭제합니다. 둘 다 Effec에 중요합니다

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

에디트플러스 중국어 크랙 버전

에디트플러스 중국어 크랙 버전

작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

MinGW - Windows용 미니멀리스트 GNU

MinGW - Windows용 미니멀리스트 GNU

이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.

DVWA

DVWA

DVWA(Damn Vulnerable Web App)는 매우 취약한 PHP/MySQL 웹 애플리케이션입니다. 주요 목표는 보안 전문가가 법적 환경에서 자신의 기술과 도구를 테스트하고, 웹 개발자가 웹 응용 프로그램 보안 프로세스를 더 잘 이해할 수 있도록 돕고, 교사/학생이 교실 환경 웹 응용 프로그램에서 가르치고 배울 수 있도록 돕는 것입니다. 보안. DVWA의 목표는 다양한 난이도의 간단하고 간단한 인터페이스를 통해 가장 일반적인 웹 취약점 중 일부를 연습하는 것입니다. 이 소프트웨어는

맨티스BT

맨티스BT

Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.

SecList

SecList

SecLists는 최고의 보안 테스터의 동반자입니다. 보안 평가 시 자주 사용되는 다양한 유형의 목록을 한 곳에 모아 놓은 것입니다. SecLists는 보안 테스터에게 필요할 수 있는 모든 목록을 편리하게 제공하여 보안 테스트를 더욱 효율적이고 생산적으로 만드는 데 도움이 됩니다. 목록 유형에는 사용자 이름, 비밀번호, URL, 퍼징 페이로드, 민감한 데이터 패턴, 웹 셸 등이 포함됩니다. 테스터는 이 저장소를 새로운 테스트 시스템으로 간단히 가져올 수 있으며 필요한 모든 유형의 목록에 액세스할 수 있습니다.