이 튜토리얼에서는 주어진 수 n보다 작으면서, 모든 자릿수가 소수(2, 3, 5, 7)로만 이루어진 가장 큰 수를 찾는 프로그램을 C++로 작성해 보겠습니다.
그럼 문제를 해결하는 단계를 하나씩 살펴보겠습니다.
문제 해결 접근 방법
- 숫자의 각 자릿수를 앞에서부터 순회하며 검사합니다.
- 만약 현재 자릿수가 소수가 아니라면 다음과 같이 처리합니다.
- 해당 자릿수가 2 이하일 때는 왼쪽(앞) 자릿수로 인덱스 i를 하나씩 줄여 나갑니다. 만약 i가 음수가 되면 0으로 설정합니다.
- 현재 위치의 자릿수를 바로 아래의 가장 큰 소수 자릿수로 갱신합니다.
- 그 다음 인덱스부터 문자열 끝까지 모든 자릿수를 최댓값인 7로 채웁니다.
- 만약 현재 자릿수가 소수가 아니라면 다음과 같이 처리합니다.
- 모든 자릿수가 이미 소수라면 원래의 n을 그대로 반환합니다.
예제 코드
위의 알고리즘을 실제 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
bool isPrime(char c) {
return c == '2' || c == '3' || c == '5' || c == '7';
}
void decrease(string& n, int i) {
if (n[i] <= '2') {
n.erase(i, 1);
n[i] = '7';
}else if (n[i] == '3') {
n[i] = '2';
}else if (n[i] <= '5') {
n[i] = '3';
}else if (n[i] <= '7') {
n[i] = '5';
}else {
n[i] = '7';
}
return;
}
string getPrimeDigitsNumber(string n) {
for (int i = 0; i < n.length(); i++) {
if (!isPrime(n[i])) {
while (n[i] <= '2' && i >= 0) {
i--;
}
if (i < 0) {
i = 0;
}
decrease(n, i);
for (int j = i + 1; j < n.length(); j++) {
n[j] = '7';
}
break;
}
}
return n;
}
int main() {
string n = "7464";
cout << getPrimeDigitsNumber(n) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
7377
입력값 "7464"의 경우 세 번째 자릿수 6이 소수가 아니므로, 해당 자릿수를 5로 낮추고 그 뒤의 자릿수들을 모두 7로 채워 결과적으로 7377이 얻어집니다.
마무리
지금까지 C++을 활용해 n보다 작은 수 중에서 모든 자릿수가 소수로만 구성된 가장 큰 수를 찾는 방법을 알아보았습니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.