숫자 0부터 9까지 각 자릿수에 포함된 구멍(닫힌 공간)의 개수를 저장한 배열 holes[10]이 주어졌을 때, 입력으로 주어진 정수 안에 구멍이 총 몇 개 있는지 계산하는 문제입니다. 일반적인 숫자 모양에서 구멍의 개수는 다음과 같이 정의됩니다.
- 0 → 1개
- 4 → 1개
- 6 → 1개
- 8 → 2개
- 9 → 1개
- 나머지 숫자(1, 2, 3, 5, 7) → 0개
따라서 holes[] 배열은 다음과 같이 초기화할 수 있습니다.
holes[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 }예제
입력
number = 239143
출력
정수에 포함된 구멍의 개수: 2
설명
각 자릿수의 구멍 개수를 모두 더합니다.
239143 → (0 + 0 + 1 + 0 + 1 + 0) = 2
입력
number = 12345
출력
정수에 포함된 구멍의 개수: 1
설명
12345 → (0 + 0 + 0 + 1 + 0) = 1
접근 방법
이 문제는 간단한 자릿수 분리 기법으로 해결할 수 있습니다. 나머지 연산자(%)를 이용해 정수의 마지막 자릿수를 하나씩 추출하고, 해당 자릿수의 구멍 개수를 결과값에 더한 뒤, 정수를 10으로 나누어 다음 자릿수로 넘어갑니다. 모든 자릿수를 확인할 때까지 이 과정을 반복합니다.
- 정수를 입력받습니다.
- holes[] 배열을 초기화합니다.
- holes_integer(int number, int holes[]) 함수는 정수에 포함된 구멍의 총 개수를 반환합니다.
- count 변수를 0으로 초기화합니다.
- number가 0보다 큰 동안 반복합니다.
- temp = number % 10으로 마지막 자릿수를 구하고, count에 holes[temp] 값을 더합니다.
- number를 10으로 나누어 다음 자릿수로 이동합니다.
- 반복이 종료되면 count를 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int holes_integer(int number, int holes[]){
int count = 0;
while (number > 0){
int temp = number % 10; // 마지막 자릿수 추출
count = count + holes[temp]; // 구멍 개수 누적
number = number / 10; // 다음 자릿수로 이동
}
return count;
}
int main(){
int number = 239143;
int holes[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 };
cout<<"정수에 포함된 구멍의 개수: "<<holes_integer(number, holes);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
정수에 포함된 구멍의 개수: 2
복잡도 분석
시간 복잡도는 정수의 자릿수에 비례하므로 O(log N)이며, 추가로 사용하는 메모리는 상수 공간인 O(1)입니다. 참고로 이 알고리즘은 양의 정수를 기준으로 동작하며, 음수를 처리해야 하는 경우에는 먼저 절댓값으로 변환한 뒤 적용하면 됩니다.