n개의 요소를 가진 배열 A와 하나의 숫자 k가 주어졌다고 가정해 보겠습니다. 여기서 행운의 숫자(lucky number)란 십진수 표현에서 오직 행운의 자릿수인 4와 7만으로 이루어진 양의 정수를 의미합니다. 우리가 구해야 할 것은 주어진 n개의 양의 정수 중에서, 4 또는 7로 이루어진 자릿수(행운의 자릿수)가 k개 이하인 수가 몇 개인지 세는 것입니다.
예를 들어 입력이 A = [44, 74, 474, 154], k = 2라고 해봅시다. 이때 출력은 3이 됩니다.
- 44: 행운의 자릿수 2개 (4, 4) → 조건 만족
- 74: 행운의 자릿수 2개 (7, 4) → 조건 만족
- 474: 행운의 자릿수 3개 (4, 7, 4) → k보다 많아 제외
- 154: 행운의 자릿수 1개 (4) → 조건 만족
따라서 조건을 만족하는 수는 44, 74, 154로 총 세 개입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 배열 A의 크기를 n에 저장하고, 결과를 담을 변수 f를 0으로 초기화합니다.
- 각 요소 A[i]에 대해 마지막 자릿수부터 한 자리씩 확인하며, 해당 자릿수가 4 또는 7이면 카운터 c를 1 증가시킵니다.
- A[i]를 10으로 나누어 모든 자릿수를 검사할 때까지 반복합니다.
- 행운의 자릿수 개수 c가 k 이하이면 f를 1 증가시킵니다.
- 모든 요소를 검사한 후 f를 반환합니다.
n := A의 크기
f := 0
i := 0부터 i < n까지 반복 (i는 1씩 증가):
c := 0
A[i]가 0이 아닌 동안 반복:
만약 A[i] mod 10이 4 또는 7이라면:
c를 1 증가
A[i] := A[i] / 10
만약 c <= k라면:
f를 1 증가
f 반환
C++ 구현 예제
아래 코드를 통해 더 잘 이해할 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k){
int n = A.size();
int f = 0;
for (int i = 0; i < n; ++i){
int c = 0;
while (A[i] != 0){
if (A[i] % 10 == 4 || A[i] % 10 == 7)
c++;
A[i] /= 10;
}
if (c <= k)
f++;
}
return f;
}
int main(){
vector<int> A = {44, 74, 474, 154};
int k = 2;
cout << solve(A, k) << endl;
}
입력
{44, 74, 474, 154}, 2
출력
3
복잡도 분석
각 숫자에 대해 자릿수만큼 검사를 수행하므로, 숫자의 최대 자릿수를 d라고 하면 시간 복잡도는 O(n × d)입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)로 매우 효율적입니다.