문제
N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 수를 출력하는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력 한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다. 뒤집는 함수인 int reverse(int x) 와 소수인지를 확인하는 함수 bool isPrime(int x)를 반드시 작성하여 프로그래밍 한다.
💡 입력설명
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 100,000를 넘지 않는다.
💡 출력설명
첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.
💡 입력예제
5 32 55 62 3700 250
💡 출력예제
23 73
코드
첫 번째 풀이
#include <stdio.h>
#include <math.h>
int reverse(int x) {
int i, cnt = 0, tmp, rem, res = 0;
tmp = x;
while(tmp > 0) {
tmp /= 10;
cnt++;
}
tmp = x;
for(i = cnt; i >= 1; i--) {
rem = tmp % 10;
tmp /= 10;
res += rem * pow(10, cnt - 1);
cnt--;
}
return res;
}
bool isPrime(int x) {
int i;
if(x == 1) {
return false;
}
for(i = 2; i < x; i++) {
if(x % i == 0) {
return false;
}
}
return true;
}
int main () {
int n, i, input, val, tf;
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d", &input);
val = reverse(input);
tf = isPrime(val);
if(tf == true) {
printf("%d ", val);
}
}
return 0;
}최종 풀이
#include <stdio.h>
int reverse(int x) {
int i, rem, res = 0;
while(x > 0) {
rem = x % 10;
res = res * 10 + rem;
x /= 10;
}
return res;
}
bool isPrime(int x) {
int i;
if(x == 1) {
return false;
}
for(i = 2; i < x; i++) {
if(x % i == 0) {
return false;
}
}
return true;
}
int main () {
int n, i, input, val, tf;
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d", &input);
val = reverse(input);
tf = isPrime(val);
if(tf == true) {
printf("%d ", val);
}
}
return 0;
}
설명
사용자로부터 n을 입력받고 n만큼 입력받기 위해 n번 반복하는 for문을 작성한다.
각 입력받은 값을 reverse함수에 인자로 전달한다.
이후 int형을 반환하고 int x를 매개변수로 받는 reverse함수를 선언한다.
사용자로부터 입력받은 x가 0보다 클 경우만 반복하는 while문을 작성한다.
x를 10으로 나눴을 때 나머지 값을 rem에 할당하고 loop를 돌 때마다 나머지가 0보다 큰 숫자는 10씩 곱해나가며 res에 누적한다. 이후 res값을 return한다.
return받은 res값을 main함수에서의 val에 할당한다. 해당 val값의 소수를 판별하기 위해 isPrime함수의 인자로 전달한다.
이후 bool형을 반환하고 int x를 매개변수로 받는 isPrime함수를 선언한다.
만약 x가 1일 경우 소수에 해당하지 않으므로 false를 return하고 해당 함수를 종료한다.
1이 아닐 경우 해당 x값이 2~x-1값 중에 하나라도 나누어 떨어진다면 소수가 아니므로 false를 return하고 그렇지 않을 경우 true를 return하고 함수를 종료한다.
return받은 boolean값을 main함수에서의 tf에 할당한다. 마지막으로 해당 tf가 true일 경우에만 val을 출력하도록 한다.
배운 점
1. 0을 고려한 숫자 뒤집기 부분에서 각 자리의 수를 따로 for문을 통해 구하고 그만큼 반복하는 for문을 2번 작성하였는데 수학적으로 접근하여 식을 세우면 간단하게 구현할 수 있다는 것을 알게되었다.
※ 0을 고려한 숫자 뒤집기
int i, rem, res = 0; while(x > 0) { rem = x % 10; res = res * 10 + rem; x /= 10; }
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
