Count Even Numbers

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

2 로 나눈 나머지가 0인지 확인합니다: x % 2 == 0 . 이는 대부분의 주류 언어에서 양수, 음수, 0 모두에 적용됩니다. 다른 방법으로는 가장 낮은 비트를 확인할 수 있습니다. 짝수는 0 비트로 끝나므로 (x & 1) == 0 을 사용합니다.

Q: 0은 짝수인가요?

맞습니다. 0을 2 로 나누면 나머지 없이 0 이 되므로 짝수의 정의에 부합합니다. 또한 홀수인 -1 과 1 사이에 있으며, 짝수가 정확히 있어야 할 위치에 있습니다.

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

카운터를 사용해 한 번 순회하면 O(n) 시간이 걸리고 추가 공간은 O(1) 만큼 사용합니다. 모든 값을 확인해야 하므로 O(n) 보다 빠른 방법은 없습니다. 먼저 필터링된 목록을 만들면 같은 개수를 얻지만 추가 메모리를 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입니다.

제출 시 숨은 테스트 +12개

후속 질문

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

힌트

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

3개 중 0개 열림

풀이

반복문은 한 줄이면 됩니다. 풀이가 틀리는 부분은 짝수 여부 검사입니다. 많은 언어에서 음수의 나머지는 음수이므로, -3 % 2는 -1입니다. x % 2 == 0을 검사하면 어떤 언어에서든 부호와 관계없이 올바르게 판별할 수 있으며, 카운터를 누적해도 추가 메모리가 필요하지 않습니다.

짝수 값을 수집한 다음 개수를 세세요

핵심 아이디어

작업을 두 단계로 나누세요. 짝수 값을 골라낸 다음, 골라낸 값의 개수를 세세요. 값 x는 x % 2 == 0일 때 짝수입니다. 대부분의 언어에는 새 목록을 한 줄로 만드는 필터 함수가 있으며, 그 목록의 길이가 답입니다. [3, 8, 12, 5, 6]의 경우 필터링된 목록은 [8, 12, 6]이므로 답은 3입니다.

이 방법은 올바르고 읽기 쉽지만, 새 목록을 만들려면 O(n) 메모리가 필요합니다. 여기서는 최대 5000개의 값을 저장하지만, 그 길이는 한 번만 읽습니다. 값 자체는 그 뒤로 다시 사용되지 않습니다.

알고리즘

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

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

실행 중인 카운터로 세기

핵심 아이디어

목록 대신 카운터를 유지하세요. 카운터를 0으로 시작하고 각 값을 한 번씩 확인한 다음, 값이 짝수이면 1을 더하세요. 모든 값을 정확히 한 번씩 확인하므로 개수는 정확하며, 필요한 메모리는 정수 하나뿐입니다.

이 조건은 주의해서 살펴봐야 합니다. C, C++, Java, C#, JavaScript, Go, Rust, Swift 및 PHP에서는 나머지의 부호가 수의 부호를 따르므로 -3 % 2는 1이 아니라 -1입니다. 짝수는 부호와 관계없이 나머지가 0이므로 x % 2 == 0은 항상 올바르지만, 홀수를 x % 2 == 1로 검사하면 음수 홀수를 모두 놓칩니다. [-4, -3, 0, 7]의 나머지는 각각 0, -1, 0, 1이므로 카운터는 2가 됩니다.

0도 셉니다. 0 % 2는 0이므로 0은 짝수입니다.

알고리즘

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

함정과 경계 사례

여기서 버그는 음수와 0에서 비롯됩니다.

x % 2 == 1을 사용해 홀수를 세고 길이에서 빼는 경우입니다. C 계열 언어에서는 -3 % 2가 -1이므로 -3은 홀수로 세어지지 않고 짝수로 계산됩니다.
0을 짝수도 홀수도 아닌 것으로 취급하는 경우입니다. 0 = 2 × 0이므로 0은 짝수이며, [0]은 1을 반환합니다.
비트 검사를 x & 1 == 0으로 작성하는 경우입니다. C, C++ 및 JavaScript에서는 ==의 우선순위가 &보다 높으므로, 이는 x & (1 == 0)을 의미합니다. 이 결과는 항상 0이므로 아무것도 세지 않습니다. (x & 1) == 0으로 작성하세요.
인덱스가 0부터 시작하는 언어에서 루프를 인덱스 1부터 시작해 첫 번째 값을 건너뛰거나, 첫 번째 값의 인덱스가 1인 Lua와 R에서 0부터 시작하는 경우입니다.

자주 묻는 질문4

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

2로 나눈 나머지가 0인지 확인합니다: x % 2 == 0. 이는 대부분의 주류 언어에서 양수, 음수, 0 모두에 적용됩니다. 다른 방법으로는 가장 낮은 비트를 확인할 수 있습니다. 짝수는 0 비트로 끝나므로 (x & 1) == 0을 사용합니다.

0은 짝수인가요?

맞습니다. 0을 2로 나누면 나머지 없이 0이 되므로 짝수의 정의에 부합합니다. 또한 홀수인 -1과 1 사이에 있으며, 짝수가 정확히 있어야 할 위치에 있습니다.

음수에서는 왜 x % 2 == 1이 작동하지 않을까요?

C, C++, Java, C#, JavaScript, Go, Rust, Swift, PHP에서는 나머지가 나누어지는 수의 부호를 따르므로 -3 % 2는 -1입니다. 반면 Python, Ruby, Dart, Lua, R에서는 1을 반환합니다. 홀수인지 확인할 때는 x % 2 != 0을, 짝수인지 확인할 때는 x % 2 == 0을 검사하면 어느 언어에서나 같은 결과를 얻습니다.

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

카운터를 사용해 한 번 순회하면 O(n) 시간이 걸리고 추가 공간은 O(1)만큼 사용합니다. 모든 값을 확인해야 하므로 O(n)보다 빠른 방법은 없습니다. 먼저 필터링된 목록을 만들면 같은 개수를 얻지만 추가 메모리를 O(n)만큼 사용합니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

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

기대값