Count Even Numbers

Q: 코드에서 숫자가 짝수인지 어떻게 확인하나요?

2 로 나눈 나머지가 0인지 확인하세요: x % 2 == 0 . -3 % 2 가 -1 인 언어에서도 양수, 음수, 0 모두에 대해 작동합니다. (x & 1) == 0 으로 최하위 비트를 확인할 수도 있습니다.

Q: 0은 짝수인가요?

맞습니다. 0을 2 로 나누면 나머지 없이 0 이 되므로 짝수의 정의에 부합합니다. 또한 짝수가 속하는 홀수 -1 과 1 사이에 있습니다.

Q: 배열에서 짝수의 개수를 세는 시간 복잡도는 무엇인가요?

카운터를 사용한 한 번의 순회에는 O(n) 시간이 걸리고 추가 공간은 O(1) 입니다. 모든 값을 확인해야 하므로 O(n) 보다 빠른 방법은 없습니다.

입문배열과 문자열 수학과 시뮬레이션

+10

비어 있지 않은 정수 목록 nums가 주어지면, 그중 짝수인 값의 개수를 반환하세요. 어떤 수를 2로 나누었을 때 나머지가 없으면 짝수이며, 여기에는 0과 -4와 같은 음수도 포함됩니다.

함수

countEvens(nums: integer-array) → integer

numsinteger-array: 확인할 정수 목록
반환값integer: nums에서 짝수 값의 개수

제약 조건

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

예제

입력: nums = [3, 8, 12, 5, 6]
출력: 3
설명: 8, 12, 6은 2로 나누어떨어지지만, 3과 5는 그렇지 않습니다. 답은 3입니다.

입력: nums = [-4, -3, 0, 7]
출력: 2
설명: -4 = 2 × (-2)와 0 = 2 × 0이므로 둘 다 짝수입니다. -3과 7은 홀수이고, 개수는 2입니다.

입력: nums = [1, 9, 15]
출력: 0
설명: 1, 9, 15는 모두 홀수이므로 답은 0입니다.

후속 질문

다음과 같은 질문을 많이 받습니다. 인덱스 l과 인덱스 r 사이에 짝수 값이 몇 개 있나요? nums를 한 번 순회한 뒤, 각 질문에 O(1) 시간으로 답할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

각 값을 한 번씩 확인하고 2로 나누었을 때 나머지가 0인 값의 개수를 세세요. 나머지를 1과 비교해 홀수인지 확인하는 대신 0과 비교하면 음수도 올바르게 처리할 수 있습니다.

짝수 값을 모은 다음, 개수를 세세요

핵심 아이디어

필터를 사용해 짝수 값을 골라낸 다음, 결과의 길이를 반환하세요. [3, 8, 12, 5, 6]의 경우 필터링된 목록은 [8, 12, 6]이므로 답은 3입니다.

시간 복잡도는 O(n)이지만, 새 목록은 길이를 한 번만 읽기 위해 최대 5000개의 값만큼 O(n)의 메모리를 사용합니다.

알고리즘

nums의 모든 x 중 x % 2 == 0인 항목을 담는 새 리스트를 만드세요.
그 리스트의 길이를 반환하세요.

def countEvens(nums):
    evens = [x for x in nums if x % 2 == 0]
    return len(evens)

계속 증가하는 카운터로 세기

핵심 아이디어

리스트 대신 카운터를 사용하고, x % 2 == 0인 각 값마다 1을 더하세요. 짝수는 부호와 관계없이 나머지가 0이므로, 모든 언어에서 -4와 0에 대해 이 조건이 성립합니다. 홀수를 판별하는 조건을 x % 2 == 1로 작성하면 그렇지 않습니다. C, Java, JavaScript 및 대부분의 C 계열 언어에서는 나머지의 부호가 수의 부호를 따르므로 -3 % 2는 -1입니다.

한 번 순회하고 정수 하나만 사용합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.

알고리즘

count를 0으로 설정합니다.
nums의 모든 값 x를 반복합니다.
x % 2 == 0이면 count에 1을 더합니다.
반복이 끝난 후 count를 반환합니다.

def countEvens(nums):
    count = 0
    for x in nums:
        if x % 2 == 0:  # 0 also works for negatives, where the remainder can be -1
            count += 1
    return count

함정과 경계 사례

x % 2 == 1을 사용해 홀수 값을 세고 길이에서 빼는 방법입니다. C 계열 언어에서는 -3 % 2가 -1이므로, [-3]은 0이 아니라 1을 반환합니다.
0을 짝수도 홀수도 아닌 것으로 취급하는 방법입니다. 0 = 2 × 0이므로, [0]은 1을 반환합니다.
비트 검사를 x & 1 == 0으로 작성하는 방법입니다. C, C++, JavaScript에서는 ==가 &보다 우선순위가 높으므로, 이는 x & (1 == 0)을 의미합니다. 이 식은 항상 0이므로 아무것도 세지 않습니다. (x & 1) == 0으로 작성하세요.

자주 묻는 질문3

코드에서 숫자가 짝수인지 어떻게 확인하나요?

2로 나눈 나머지가 0인지 확인하세요: x % 2 == 0. -3 % 2가 -1인 언어에서도 양수, 음수, 0 모두에 대해 작동합니다. (x & 1) == 0으로 최하위 비트를 확인할 수도 있습니다.

0은 짝수인가요?

맞습니다. 0을 2로 나누면 나머지 없이 0이 되므로 짝수의 정의에 부합합니다. 또한 짝수가 속하는 홀수 -1과 1 사이에 있습니다.

배열에서 짝수의 개수를 세는 시간 복잡도는 무엇인가요?

카운터를 사용한 한 번의 순회에는 O(n) 시간이 걸리고 추가 공간은 O(1)입니다. 모든 값을 확인해야 하므로 O(n)보다 빠른 방법은 없습니다.

def countEvens(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [3, 8, 12, 5, 6]

예상 출력