0부터 진법 B까지의 모든 숫자를 포함하는 수를 해당 진법의 판디지털(Pandigital) 숫자라고 합니다. 다만 일부 숫자는 1부터 9까지만 포함하는데, 이러한 수는 무영 판디지털(zeroless pandigital) 숫자라고 부릅니다. 판디지털 숫자의 대표적인 예로는 0123456789, 0789564312 등이 있습니다.
이 튜토리얼에서는 하나의 숫자와 진법이 주어졌을 때, 해당 숫자가 주어진 진법에서 판디지털인지 확인하는 문제를 다룹니다.
입력: num = "9651723467380AZ", base = 10 출력: YES 설명: num은 10진법의 모든 숫자, 즉 0부터 9까지 모두 포함하고 있으므로 판디지털 숫자입니다. 입력: num = "130264ABCDE745789", base = 16 출력: NO 설명: num에는 16진법에 속한 F(15)가 포함되어 있지 않으므로 판디지털 숫자가 아닙니다.
문제 해결 접근 방식
이 문제를 해결하기 위해 Set(집합) 자료구조를 사용합니다. 중복 없이 고유한 값만 저장하면 되기 때문입니다. 전체적인 풀이 과정은 다음과 같습니다.
문자열을 순회하며 한 번에 한 문자씩 처리합니다.
각 문자가 숫자인지 알파벳인지 확인합니다.
알파벳이라면 해당 문자의 알파벳 상 위치에 10을 더해 두 자릿수 값을 나타냅니다. 예를 들어 'A'는 10, 'B'는 11처럼 변환됩니다.
변환된 값을 집합(Set)에 저장합니다.
순회가 끝난 후, 집합의 크기가 진법(base)과 같은지 확인합니다. 같다면 모든 자릿수가 존재한다는 의미입니다.
예제 코드
위 접근 방식의 C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
int main(){
int base = 10;
char n[] = "9651723467380AZ";
// 고유한 값을 저장할 집합 선언
set<int, greater<int> > s;
// 문자열을 순회합니다.
for (int i = 0; i < strlen(n); i++){
// 요소가 숫자인지 확인
if (n[i] >= '0' && n[i] <= '9')
s.insert(n[i]- '0');
// 요소가 알파벳인지 확인
else if (n[i] - 'A' <= base - 11)
s.insert(n[i] - 'A' + 10) ;
}
// 모든 자릿수가 존재하는지 확인
if(s.size()==base)
cout<< "YES";
else
cout<< "NO";
return 0;
}실행 결과
YES
마무리
이 튜토리얼에서는 숫자와 진법이 주어졌을 때 해당 숫자가 그 진법의 판디지털 숫자인지 확인하는 문제를 살펴보았습니다. 핵심 아이디어는 각 자릿수를 집합(Set)에 삽입한 뒤, 집합의 크기가 진법과 일치하는지 비교하는 것입니다. 이 방식은 시간 복잡도 O(N)으로 매우 효율적이며, 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 튜토리얼이 여러분의 학습에 도움이 되었기를 바랍니다.