문제 개요
숫자 n이 주어졌을 때, n을 구성하는 각 자릿수가 등장하는 횟수(빈도)가 그 자릿수의 값 자체보다 작거나 같은지 확인하는 것이 목표입니다.
예를 들어 입력이 n = 5162569라고 가정해 보겠습니다. 각 자릿수와 그 빈도는 (5, 2), (1, 1), (6, 2), (9, 1)로 나타낼 수 있습니다. 모든 빈도가 해당 자릿수의 값보다 작거나 같으므로 결과는 True가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 0부터 9까지의 각 숫자 i에 대해 반복합니다.
- 임시 변수 temp에 n을 저장하고, 카운터 cnt를 0으로 초기화합니다.
- temp가 0이 아닌 동안 다음을 반복합니다.
- temp를 10으로 나눈 나머지가 i와 같으면 cnt를 1 증가시킵니다.
- cnt가 i보다 커지면 즉시 False를 반환합니다.
- temp를 10으로 나눈 몫으로 갱신합니다.
- 모든 자릿수에 대한 검사를 통과하면 True를 반환합니다.
예제 코드
아래 구현을 통해 동작 방식을 더 쉽게 이해할 수 있습니다.
def solve(n):
for i in range(10):
temp = n
cnt = 0
while temp:
if temp % 10 == i:
cnt += 1
if cnt > i:
return False
temp //= 10
return True
s = 5162569
print(solve(s))입력
5162569
출력
True
복잡도 분석
이 알고리즘은 0부터 9까지 총 10개의 숫자에 대해 각각 n의 모든 자릿수를 한 번씩 확인하므로, 시간 복잡도는 O(10 × d)입니다. 여기서 d는 숫자 n의 자릿수입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.