Find Numbers with Even Number of Digits — 자릿수 개수의 짝수 여부 세기

스터디·7분 읽기
#알고리즘#배열#수학
시리즈#알고리즘· 19/20편
전체 보기
  1. 01Merge Strings Alternately — 단일 루프로 `O(n + m)` 교차 병합
  2. 02Increasing Triplet Subsequence — `O(n)` 시간, `O(1)` 공간으로 푸는 그리디 패턴
  3. 03Move Zeroes — 쓰기 포인터 하나로 `O(n)`/`O(1)` 제자리 재배치
  4. 04String Compression — 읽기/쓰기 포인터로 `O(n)`/`O(1)` 제자리 압축
  5. 05Product of Array Except Self — 나눗셈 없이 `O(n)`/`O(1)`로 나머지 곱 구하기
  6. 06Reverse Vowels of a String — 투 포인터 `O(n)` 스왑으로 모음만 뒤집기
  7. 07Can Place Flowers — `O(n)` 그리디 스캔으로 인접 금지 배치 판정
  8. 08시간 복잡도와 공간 복잡도 완전 정복 — Big-O 표기법부터 실전 분석까지
  9. 09Greatest Common Divisor of Strings — `GCD`로 `O(n + m)` 문자열 최대 공약 패턴
  10. 10Container With Most Water — 투 포인터 `O(n)`로 최대 넓이 한 번에 찾기
  11. 11Is Subsequence — 투 포인터 `O(|s| + |t|)`로 부분 수열 판정
  12. 12Richest Customer Wealth — 2차원 배열에서 행 합의 최댓값 찾기
  13. 13Running Sum of 1d Array — 누적합의 가장 기본 형태
  14. 14Roman to Integer — 감산 규칙을 한 번의 스캔으로 처리하기
  15. 15Palindrome Number — 문자열 없이 절반만 뒤집는 숫자 팰린드롬 판정
  16. 16Max Number of K-Sum Pairs — 정렬 `O(n log n)`에서 해시 `O(n)`까지 최대 페어 수 세기
  17. 17Ransom Note — 문자 개수로 문자열 구성 가능 여부 판정하기
  18. 18Middle of the Linked List — slow/fast 포인터로 중간 노드 찾기
  19. 19Find Numbers with Even Number of Digits — 자릿수 개수의 짝수 여부 세기읽는 중
  20. 20Max Consecutive Ones — 한 번의 스캔으로 가장 긴 1 구간 찾기

자릿수가 짝수인 수는 몇 개일까?

LeetCode 1295번 문제는 이렇게 주어집니다.

정수 배열 nums가 주어집니다. 자릿수 개수가 짝수인 원소가 몇 개인지 반환하세요.

예시는 이렇습니다.

  • nums = [12, 345, 2, 6, 7896] → 2
  • nums = [555, 901, 482, 1771] → 1

제약은 다음과 같습니다.

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^5

이 문제의 핵심은 각 수에 대해 자릿수 개수만 알면 된다는 점입니다. 값 자체의 크기 비교가 아니라, 숫자가 몇 자리인지 세고 그 개수가 짝수인지 확인하면 됩니다. 이 글에서는 문자열 변환 풀이부터, 나눗셈으로 자릿수를 세는 풀이, 그리고 제약을 이용한 범위 비교 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

문제를 자릿수 판정 문제로 바꾸기

예제 nums = [12, 345, 2, 6, 7896]를 보면:

  • 12 → 2자리 → 짝수
  • 345 → 3자리 → 홀수
  • 2 → 1자리 → 홀수
  • 6 → 1자리 → 홀수
  • 7896 → 4자리 → 짝수

따라서 답은 2입니다.

즉 문제는 결국 이렇게 바뀝니다.

각 숫자의 자릿수를 구한다
그 자릿수가 짝수인지 확인한다
짝수인 개수를 센다

배열의 각 원소는 서로 독립적이므로, 한 원소씩 판정해서 카운트하면 됩니다.

Phase 1. 문자열로 바꿔서 길이 보기

가장 먼저 떠올릴 수 있는 방법은 숫자를 문자열로 바꾼 뒤 길이를 확인하는 것입니다.

fun findNumbers(nums: IntArray): Int {
    var answer = 0

    for (num in nums) {
        if (num.toString().length % 2 == 0) {
            answer++
        }
    }

    return answer
}

이 풀이는 매우 직접적입니다.

  • 12.toString() → "12" → 길이 2
  • 345.toString() → "345" → 길이 3

문자열 길이가 짝수면 카운트를 늘리면 됩니다.

시간 복잡도는 배열 길이를 n, 한 숫자의 자릿수를 d라고 하면 O(n * d)로 볼 수 있습니다. 이 문제에서는 nums[i] <= 10^5라 자릿수는 최대 6이므로, 사실상 O(n)입니다. 추가 공간은 문자열 변환에 쓰이는 임시 공간이 있지만 자릿수 상한이 작으므로 문제 규모에서는 무시할 만합니다.

이 문제에서는 가장 짧고 이해하기 쉬운 풀이입니다. 다만 숫자를 문자열로 바꾸지 않고도 자릿수를 셀 수 있습니다.

Phase 2. 나눗셈으로 자릿수 세기

자릿수는 10으로 계속 나누면서 셀 수 있습니다.

예를 들어 7896은:

7896 -> 789 -> 78 -> 7 -> 0

처럼 4번 나누면 끝나므로 4자리입니다.

fun findNumbers(nums: IntArray): Int {
    var answer = 0

    for (num in nums) {
        if (digitCount(num) % 2 == 0) {
            answer++
        }
    }

    return answer
}

private fun digitCount(num: Int): Int {
    var x = num
    var count = 0

    while (x > 0) {
        count++
        x /= 10
    }

    return count
}

digitCount(7896)를 따라가면:

x = 7896 -> count = 1
x = 789  -> count = 2
x = 78   -> count = 3
x = 7    -> count = 4
x = 0    -> 종료

이렇게 자릿수를 구한 뒤 짝수인지 확인하면 됩니다.

시간 복잡도는 역시 O(n * d)입니다. 이 문제에서는 d <= 6이므로 사실상 O(n)입니다. 추가 공간은 O(1)입니다.

왜 x /= 10이 자릿수를 하나씩 줄이나요?

정수 나눗셈에서는 소수점 아래가 버려집니다.

예를 들어:

7896 / 10 = 789
789  / 10 = 78
78   / 10 = 7
7    / 10 = 0

매번 가장 오른쪽 자리 하나가 제거됩니다. 그래서 몇 번 나눌 수 있는지 세면 곧 자릿수 개수가 됩니다.

Phase 3. 제약을 이용해 범위로 바로 판정하기

이 문제는 nums[i] <= 10^5라고 되어 있습니다. 즉 가능한 자릿수는 많아야:

  • 1자리: 1 ~ 9
  • 2자리: 10 ~ 99
  • 3자리: 100 ~ 999
  • 4자리: 1000 ~ 9999
  • 5자리: 10000 ~ 99999
  • 6자리: 100000

입니다.

따라서 짝수 자릿수는:

  • 2자리: 10 ~ 99
  • 4자리: 1000 ~ 9999
  • 6자리: 100000

뿐입니다.

fun findNumbers(nums: IntArray): Int {
    var answer = 0

    for (num in nums) {
        if ((num >= 10 && num <= 99) ||
            (num >= 1000 && num <= 9999) ||
            num == 100000
        ) {
            answer++
        }
    }

    return answer
}

이 방식은 자릿수를 실제로 세지 않고, 숫자가 어느 범위에 속하는지만 검사합니다.

예를 들어:

  • 12는 10..99에 있으므로 짝수 자릿수
  • 7896은 1000..9999에 있으므로 짝수 자릿수
  • 345는 어느 조건도 만족하지 않으므로 홀수 자릿수

시간 복잡도는 O(n)이고, 추가 공간은 O(1)입니다.

다만 이 풀이는 현재 문제의 제약에 강하게 묶여 있습니다. 숫자 범위가 더 커지면 조건도 늘어나야 합니다. 일반성은 Phase 1이나 Phase 2가 더 좋습니다.

어떤 풀이가 가장 좋은가요?

이 문제에서는 세 풀이 모두 충분히 빠릅니다. 선택 기준은 보통 이렇습니다.

  • 가장 짧고 직관적인 코드: 문자열 길이
  • 숫자 연산으로 자릿수 원리를 직접 보여 주고 싶음: 나눗셈
  • 현재 제약을 적극 활용해 가장 상수 시간이 작은 판정: 범위 비교

실전 코딩 테스트라면 문자열 길이 풀이가 가장 읽기 쉽고 실수도 적습니다. 알고리즘 학습 관점에서는 나눗셈 풀이를 한 번 직접 써 보는 것이 도움이 됩니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력 결과 이유
[1] 0 1자리는 홀수
[10] 1 2자리는 짝수
[999] 0 3자리는 홀수
[1000] 1 4자리는 짝수
[99999] 0 5자리는 홀수
[100000] 1 6자리는 짝수

특히 100000이 중요합니다. 이 문제의 최댓값이고, 유일한 6자리 수 범위의 끝점입니다.

세 풀이를 다시 비교

풀이 시간 공간 특징
문자열 길이 확인 사실상 O(n) 자릿수만큼의 임시 공간 가장 짧고 직관적
나눗셈으로 자릿수 세기 사실상 O(n) O(1) 자릿수 원리를 직접 드러냄
범위 비교 O(n) O(1) 현재 문제 제약을 가장 직접적으로 활용

마무리

  1. 이 문제는 배열 문제이지만 핵심은 각 숫자의 자릿수 판정입니다 — 자릿수만 알면 짝수 여부를 바로 알 수 있습니다
  2. 문자열로 바꿔 길이를 보는 풀이가 가장 단순합니다 — 이 문제에서는 충분히 빠르고 읽기 쉽습니다
  3. 10으로 계속 나누면 자릿수를 셀 수 있습니다 — 오른쪽 자리 하나씩 제거되는 원리입니다
  4. 현재 제약에서는 짝수 자릿수 범위를 직접 비교할 수도 있습니다 — 10..99, 1000..9999, 100000
  5. 문제 제약에 덜 묶이는 일반적인 해법은 문자열 길이 또는 나눗셈 풀이입니다 — 범위 비교는 문제 조건이 바뀌면 함께 수정해야 합니다
← 목록으로
공유
이전 편

Middle of the Linked List — slow/fast 포인터로 중간 노드 찾기

다음 편

Max Consecutive Ones — 한 번의 스캔으로 가장 긴 1 구간 찾기

다음으로 읽어볼 글

스터디

Max Consecutive Ones — 한 번의 스캔으로 가장 긴 1 구간 찾기

이진 배열에서 가장 긴 연속된 1의 길이를 구하는 LeetCode 485번, 구간을 매번 다시 세는 `O(n²)` 풀이부터 현재 길이와 최댓값만 유지하는 `O(n)` 풀이까지 정리합니다.

#알고리즘#배열
·6분
스터디

Palindrome Number — 문자열 없이 절반만 뒤집는 숫자 팰린드롬 판정

정수가 앞에서 읽어도 뒤에서 읽어도 같은지 판정하는 LeetCode 9번, 문자열 변환 풀이부터 전체 숫자 뒤집기, 오버플로우 걱정을 줄이는 절반 뒤집기 `O(log x)` 풀이까지 정리합니다.

#알고리즘#수학
·7분
스터디

Roman to Integer — 감산 규칙을 한 번의 스캔으로 처리하기

로마 숫자 문자열을 정수로 바꾸는 LeetCode 13번, 감산 조합을 직접 처리하는 풀이부터 왼쪽→오른쪽 lookahead, 오른쪽→왼쪽 스캔 `O(n)` 풀이까지 정리합니다.

#알고리즘#수학
·11분