숫자가 하나 주어졌을 때, 그 숫자가 행운의 숫자(Lucky Number)에 해당하는지 판별하고 그 결과를 출력하는 것이 이번 글의 목표입니다.
행운의 숫자란 무엇일까요?
행운의 숫자는 모든 자릿수가 서로 다른 숫자를 의미합니다. 만약 하나라도 반복되는 자릿수가 존재한다면, 그 숫자는 행운의 숫자로 간주되지 않습니다.
예시
입력: n = 1234 출력: 행운의 숫자입니다 설명: 숫자 n에는 반복되는 자릿수가 없으므로 행운의 숫자입니다 입력: n = 3434 출력: 행운의 숫자가 아닙니다 설명: 숫자 n에서 3과 4가 각각 두 번씩 반복되므로 행운의 숫자가 아닙니다
프로그램의 접근 방식
- 판별할 숫자 n을 사용자로부터 입력받습니다
- 숫자의 자릿수 크기만큼 전체 자릿수를 순회합니다
- 방문한 자릿수를 표시(mark)하고, 이미 등장한 적이 있는지 확인합니다
- 해당 숫자가 행운의 숫자인지 여부를 출력합니다
알고리즘
Start
Step1-> 주어진 숫자가 행운의 숫자인지 확인하는 함수 선언
bool check_lucky(int size)
bool arr[10] 선언
Loop For int i=0 and i<10 and i++
Set arr[i] = false
End
Loop While(size > 0)
declare int digit = size % 10
IF (arr[digit])
return false
End
Set arr[digit] = true
Set size = size/10
End
return true
Step 2-> In main()
Declare int arr[] = {0,34,2345,1249,1232}
calculate int size = sizeof(arr)/sizeof(arr[0])
Loop For int i=0 and i<size and i++
check_lucky(arr[i])?
print is Lucky : print is not Lucky
End
StopC++ 구현 예제
#include<iostream>
using namespace std;
// 행운의 숫자이면 true를 반환합니다.
bool check_lucky(int size) {
bool arr[10];
for (int i=0; i<10; i++)
arr[i] = false;
while (size > 0) {
int digit = size % 10;
if (arr[digit])
return false;
arr[digit] = true;
size = size/10;
}
return true;
}
int main() {
int arr[] = {0,34,2345,1249,1232};
int size = sizeof(arr)/sizeof(arr[0]);
for (int i=0; i<size; i++)
check_lucky(arr[i])? cout << arr[i] << " is Lucky \n": cout << arr[i] << " is not Lucky \n";
return 0;
}출력 결과
0 is Lucky 34 is Lucky 2345 is Lucky 1249 is Lucky 1232 is not Lucky
코드 동작 원리
이 알고리즘은 크기가 10인 불린(Boolean) 배열 arr[10]을 활용하여 각 자릿수(0~9)의 등장 여부를 기록합니다. 숫자를 오른쪽 끝자리부터 한 자릿수씩 추출(size % 10)하면서, 해당 자릿수가 이미 등장한 적이 있다면 즉시 false를 반환합니다. 중복이 없다면 해당 자릿수를 true로 표시한 뒤 다음 자릿수로 넘어갑니다(size / 10). 모든 자릿수를 확인할 때까지 중복이 발견되지 않으면 true를 반환하여 행운의 숫자임을 알립니다.
이 방법의 시간 복잡도는 숫자의 자릿수에 비례하는 O(log n)이며, 고정된 크기의 배열만 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다.