오늘은 2283. Check if Number Has Equal Digit Count and Digit Value 문제를 풀었다.
사실 아직 알고리즘이 낯설고 어렵게만 느껴지지만, 요즘 들어 점점 “이거 생각보다 재밌는걸?“이라는 생각이 든다. 어떤 문제를 해결하기 위해 단계적으로 사고를 확장해 나가는 과정이 마치 수학문제를 푸는 듯한 느낌이 있다.
오늘은 특히 도움 없이 내 힘으로 끝까지 이해해보자!는 결심으로 문제에 임했는데, 다행히 생각을 정리하기에 적당한 문제였다.
🔍 문제 이해하기
이 문제는 숫자로 구성된 문자열이 주어졌을 때, 각 자리의 값이 그 인덱스에 해당하는 숫자가 문자열에서 나타나는 횟수와 같은지 확인하는 문제다.
예를 들어 "1210"이라는 문자열이 있다고 할 때,
- 인덱스 0의 값은 1 → 문자열 내에 0이 1번 등장한다 ✅
- 인덱스 1의 값은 2 → 문자열 내에 1이 2번 등장한다 ✅
- 인덱스 2의 값은 1 → 문자열 내에 2가 1번 등장한다 ✅
- 인덱스 3의 값은 0 → 문자열 내에 3이 0번 등장한다 ✅
모든 조건을 만족하므로 이 문자열은 true를 반환해야 한다.
✅ 구현한 해결책
func digitCount(num: String) -> Bool {
let target = num.map { String($0) }
for (index, value) in target.enumerated() {
guard "\(target.filter { $0 == "\(index)" }.count)" == value else {
return false
}
continue
}
return true
}💡 해결 과정 설명
- 문자열을 개별 문자 배열로 변환한다:
num.map { String($0) } - 배열을 순회하면서 각 자릿수(index)와 값(value)을 확인한다.
- 현재 인덱스 값이 문자열에 나타나는 횟수를 계산한다:
target.filter { $0 == "\(index)" }.count - 계산된 횟수가 현재 자릿수의 값과 같은지 확인한다.
- 모든 자릿수가 조건을 만족하면 true를 반환한다.
⚠️ 고려한 효율성
직관적으로는 잘 작동하지만, 시간 복잡도를 생각해보면 약간 아쉬운 부분이 있다.
외부에서 for 루프를 돌고, 내부에서 filter를 통해 전체 배열을 다시 순회하기 때문에 결과적으로 O(n²)의 시간 복잡도를 가진다.
시간 복잡도 최적화는 아직 어렵게 느껴졌지만, 최소한 이게 비효율적이라는 점은 손으로 계산해보며 스스로 캐치할 수 있었다.
🤚 도와줘, Chat gpt
조금 더 나은 방법이 있을까 궁금해서 결국 ChatGPT에게 도움을 요청했다.
그 결과, 딕셔너리(해시)를 사용하면 시간 복잡도를 O(n)으로 줄일 수 있다는 힌트를 얻었다.
이때 특히 유용했던 Swift 문법은 dictionary[key, default: 0] 표현이었다.
기존에는 딕셔너리에 없는 키에 접근하면 nil이 되기 때문에 옵셔널 바인딩이 필요했지만, 이 문법을 사용하면 기본값을 지정해줄 수 있어 코드가 훨씬 깔끔해진다!
func digitCount(num: String) -> Bool {
// 1. 각 숫자의 발생 횟수를 계산합니다 (O(n))
var digitCounts = [Int: Int]()
for char in num {
if let digit = Int(String(char)) {
digitCounts[digit, default: 0] += 1
}
}
// 2. 각 자릿수의 값과 해당 인덱스가 나타나는 횟수를 비교합니다 (O(n))
for (index, char) in num.enumerated() {
let expectedCount = Int(String(char)) ?? 0
let actualCount = digitCounts[index, default: 0]
if expectedCount != actualCount {
return false
}
}
return true
}💡 오늘의 교훈
- 인덱스와 값의 명확한 분리가 문제 이해에 핵심이었다.
- filter를 활용한 배열 처리는 직관적이고 강력한 도구지만, 효율성을 생각해야 한다.
- 딕셔너리 활용을 통해 시간 복잡도를 획기적으로 줄일 수 있다는 점이 인상 깊었다.
- Swift의 dictionary[key, default:] 문법은 정말 유용하고, 가독성도 높아진다.
- 무엇보다 스스로 풀어보려고 한 노력이 가장 뿌듯했다. 이해되지 않는 부분은 외부 도움을 받더라도, 문제를 끝까지 자기 식으로 해석하려는 태도가 중요하다는 걸 다시 느꼈다.
지금은 비록 초보지만, 이렇게 하나씩 쌓아가다 보면 언젠가 더 어려운 문제도 두려움 없이 마주할 수 있을 것 같다.
