leetcode 2283. Check if Number Has Equal Digit Count and Digit Value 문제 풀이

문제

https://leetcode.com/problems/check-if-number-has-equal-digit-count-and-digit-value/description/

풀이 코드 v1 : 배열

class Solution {
    func digitCount(_ num: String) -> Bool {
        let numCount = num.count
        var digitCountStorage: [Int] = Array(repeating: 0, count: numCount)
        for digit in num {
            let digitNum = Int(String(digit))!
            if numCount > digitNum {
                digitCountStorage[digitNum] += 1
            } else {
								return false 
            }
        }
        let result = digitCountStorage.map({ String($0) }).joined()
        return result == num
    }
}

다른 방식으로 풀 수 있을까?

1. 풀이 접근 방식

단순 배열로 카운팅을 하다보니 인덱스로 접근해야 하고, Array(repeating:count:)와 같이 미리 배열에 필요한 만큼의 인덱스 값을 초기화해야해서 실행 로직에 인덱스 접근이 가능한지에 대한 확인 코드도 필요합니다. 여러모로 불필요한 코드들이 생길 수 있겠죵?

해당 문제의 키워드가 “해시”이듯이, 이러한 부분은 개선하기 위해 해시 알고리즘 구조로 접근하여 풀이를 해보기로 했습니다.

🔸해시 알고리즘
입력데이터를 키로 하여 고정된 크기의 해시값으로 매핑하는 함수로, 동일한 입력에 대해 항상 동일한 해시값을 반환하는 것을 보장합니다.
🔸해시 테이블
해시 알고리즘을 이용해서 데이터를 저장하는 자료구조로, 키-값 쌍을 저장하는 자료구조입니다. Swift에서는 Dictionary와 같습니다. 해시 함수를 통해 각 키에 대해 해시값을 계산하여 배열의 인덱스 혹은 버킷을 결정합니다. 키를 통해 값에 접근하기 때문에 삽입/삭제/탐색 연산이 O(1)의 시간을 보장합니다.

 

Array → Dictionary 변경을 통해 인덱스 접근이 아닌 키 접근으로 값의 삽입/삭제/탐색 연산을 하여 안전성을 보장하게 되었고, 코드 간소화를 통해 가독성도 향상시킬 수 있었습니다.

2. 타입 변환

`let digitNum = Int(String(digit))!`와 같이 두 번의 타입 변환이 중첩되어 가독성을 저하시켰습니다. 이번에 처음 알게 된 내장 프로퍼티인데, Character 타입의 `wholeNumberValue` 프로퍼티를 통해 바로 Int 타입의 값을 얻을 수 있게 되었고 `isWholeNumber`와 같은 소소하게 유익한 내장 프로퍼티들을 추가로 확인할 수 있었습니다.

풀이 코드 v2 : 해시테이블

class Solution {
    func digitCount(_ num: String) -> Bool {
        let numCount = num.count
        var digitCount: [Int: Int] = [:]
        for char in num {
            guard let digit = char.wholeNumberValue else { return false }
            digitCount[digit, default: 0] += 1
        }
        let result = Array(0..<numCount).map({String(digitCount[$0, default: 0])}).joined()
        return result == num
    }
}

⏱️ 시간복잡도

• 시간복잡도는 문자열 순회로 O(n)이 발생하고 일련의 연산 로직들은 모두 O(1)이기 때문에, O(n)으로 v1과 v2가 동일합니다.

📦 공간복잡도

• 카운팅을 위한 배열/딕셔너리로 인해 v1과 v2 모두 O(n)의 공간복잡도 발생하지만, 문자열 크기만큼 배열의 크기를 초기화하는 배열과 실제 등장하는 숫자만큼 키가 생성되는 딕셔너리의 차이가 있을 수 있습니다.

💨 실행속도

• 배열은 연속된 메모리 공간에 데이터를 저장하므로 인덱스 접근이 매우 빠르고 Dictionary에 비해 상수시간 오버헤드가 낮습니다. 반면에 Ditionary는 내부 해시 계산과 충돌 해결 과정에서 약간의 오버헤드가 발생할 수 있습니다.

📀 메모리

• 배열은 고정된 크기의 연속된 메모리를 사용하고, Ditionray는 내부적으로 해시버킷과 관련된 오버헤드를 포함합니다. 배열에 비해 Dictionary 메모리 사용량이 다소 증가할 수 있으며 메모리 할당 방식이 비연속적일 수 있습니다.

🫧 정리

• 문제의 데이터 범위가 제한적인 경우 배열 카운팅(v1) 코드가 더 단순하고 약간의 이점을 가질 수 있지만, 범위가 불규칙하거나 키의 종류가 많아질 가능성이 있는 경우에는 해시테이블(v2) 코드가 더 유연할 수 있습니다.

회고

• 문제의 키워드가 해시임을 알았음에도 나의 사고력으로 풀고자 시도했고, 결과는 그리 나쁘지 않았다. 다만 해시알고리즘과 해시테이블의 정의와 관계성을 알게 되었고, 두 접근방식으로 모두 풀이를 했을 때 프로그래밍 측면에서는 차이가 미미하여 잘 모르겠지만 가독성과 코드표현력 측면에서는 해시테이블이 좀 더 개선된 코드라고 생각했다. 몰랐던 내장 프로퍼티가 꽤 많은 것을 알고리즘 풀이하면서 깨달았고, 문제깡을 하면서 알아놔야 코테를 볼 때 IDE 없이도 풀 수 있을 것 같다.