백준 1747번 소수&팰린드롬 - C언어

전ㄴㅇ

백준 1747번 소수 & 팰린드롬

특정 숫자를 입력할 시(1<= N <= 1,000,000) N보다 같거나 큰 소수 + 팰린드롬인 수 중 가장 작은 수를 구하는 문제이다.

입력값은 1,000,000이하의 숫자이지만 출력값은 그 이상의 값이 나올 수 있으므로 내가 답으로 내놓고자 하는 배열을 선언할 때 150만의 공간을 할당해준다. 약 6MB이므로 메모리 제한에 걸리지 않는다.

 

방식은 크게 2가지로 구성한다.

1. 소수 여부

2. 팰린드롬 여부

 

1. 소수 여부는 만약 숫자를 입력하고 수가 증가할 때마다 구할시 N개의 숫자를 검사하면 최악의 경우 O(N^2) 이므로 시간 복잡도가 너무 커져서 2초안에 계산하기에 힘들어진다. (약 2억번의 연산 안에 해결해야함)

그러므로 기초적으로 배우는 에라토스테네스의 채 방식을 이용해 소수 배열을 먼저 만들어주고 이용한다.

 

2. 팰린드롬은 앞에서부터 읽으나 뒤에서부터 읽으나 동일하므로 char 배열 타입으로 받아 처음과 끝이 같은지를 검사한다. 이 때 itoa() 의 함수를 이용하기 어려우므로 makeChar 함수를 구현했고, 어차피 팰린드롬의 경우 앞뒤가 상관없으므로 구현하기 쉽게 숫자를 거꾸로 저장했다.

C에서 itoa() 등의 함수는 compiler 에 의존하는 비표준함수이므로 백준 서버에서는 오류가 뜬다. 

---

makePrime()은 에라토스테네스의 채 방식으로 소수를 구한다.

1은 소수가 아니므로 패스하고, i=2 부터 내가 원하는 수까지 증가시키면서 숫자를 하나씩 지워간다.

j 는 1씩 증가하는 숫자이며 i와 곱해서 다음 숫자를 찾는다. 

여기서 j=i 부터 시작한 이유는 i보다 작은수는 이미 언젠가 한 번 곱했던 숫자이기 때문이다.

예를 들어서 i=5 라면 j=5 부터 시작한다. 

왜냐하면 i=5 일때 j=2 라면 i=2 일 때 j=5 인 경우에서 이미 했기 때문에 j가 i보다 작을 필요가 없기 때문이다.

//에라토스테네스의 채, 소수는 0 아니면 1
int makePrime() {
	prime[0] = prime[1] = 1;
	for (int i = 2; i <= MAX; i++) {
		if (prime[i] == 0) {
			for (int j = i; j <= MAX / i; j++) {
				prime[i * j] = 1;
			}
		}
	}
	return 0;
	
}

 

makePrime 함수의 에라토스테네스의 채 방식은  위와 같다.

만약 이미 지워진 숫자라면 표시를 해두고 i가 해당 숫자가 되었을 때 표시가 있다면 계산하지 않고 넘어간다.

어차피 소수가 아니기 때문에 해당 숫자의 배수들은 전부 지워졌을 것이기 때문이다.

 

함수를 돌리고나서 표시가 남아있지 않은 수는 모두 소수이며, 보통 소수를 1로 표시하지만 초기화의 번거로움을 피하기 위해 여기서는 0으로 표시하고 소수가 아닌 숫자에 1로 표시를 했다.

---

strlen(char *c) 함수의 경우 char 형 데이터의 경우 끝이 ascii code 로 0x0 이면 종료하는 것으로 인식하기 때문에 *c==0 이면 종료하게 했고, 글자의 숫자가 결과값으로 나온다.

#include <stdio.h>

#define MAX  1500000
int prime[MAX+10];

int strlen(char* c) {
	int ret = 0;
	while (1) {
		if (*c == 0) break;
		ret++;
		c++;
	}
	return ret;
}

---

isPelin(char *c )함수는 문자열을 받아 앞과 뒤의 숫자를 비교해 만약 다르면 0이 같으면 1이 나오도록 디자인했다.

//펠린드롬이 맞으면1 아니면0
int isPelin(char * c) {
	int len = strlen(c);
	int Pelin = 1;
	for (int i = 0; i < len; i++) {
		if (c[i] != c[len - 1 - i]) {
			Pelin = 0;
			break;
		}
	}
	if (Pelin) {
		return 1;
	}
	return 0;
}

makeChar(char *c, int N) 함수의 경우 숫자 N을 문자열 c로 변환해준다.

여기서는 팰린드롬의 여부만 중요하기 때문에 숫자를 문자열로 편하게 바꾸기 위해 숫자의 자릿수가 반대가 된다.

즉 N= 123이라면 c에는 3 부터 차례대로 들어가기 때문에 앞에서부터 읽으면 321이라는 문자열이 된다.

하지만 앞뒤가 같은지 여부만 확인하면 되므로 상관없어서 그냥 그대로 구현했다.

void makeChar(char *c,int N) {
	int idx = 0;
	while (1) {
		c[idx++] = N % 10+'0';
		N /= 10;
		if (N == 0) {
			break;
		}
	}
	c[idx] = 0x0;

}

 

전체코드

#include <stdio.h>

#define MAX  1500000
int prime[MAX+10];

int strlen(char* c) {
	int ret = 0;
	while (1) {
		if (*c == 0) break;
		ret++;
		c++;
	}
	return ret;
}

//펠린드롬이 맞으면1 아니면0
int isPelin(char * c) {
	int len = strlen(c);
	int Pelin = 1;
	for (int i = 0; i < len; i++) {
		if (c[i] != c[len - 1 - i]) {
			Pelin = 0;
			break;
		}
	}
	if (Pelin) {
		return 1;
	}
	return 0;
}

//에라토스테네스의 채, 소수는 0 아니면 1
int makePrime() {
	prime[0] = prime[1] = 1;
	for (int i = 2; i <= MAX; i++) {
		if (prime[i] == 0) {
			for (int j = i; j <= MAX / i; j++) {
				prime[i * j] = 1;
			}
		}
	}
	return 0;
	
}
//펠린드롬을 위한 char 변환이므로, 앞뒤가 바뀌어도 펠린드롬엔 문제가 없다.
void makeChar(char *c,int N) {
	int idx = 0;
	while (1) {
		c[idx++] = N % 10+'0';
		N /= 10;
		if (N == 0) {
			break;
		}
	}
	c[idx] = 0x0;

}

int main() {
	int N;
	scanf("%d", &N);
	makePrime();
	for (int i = N; i <= MAX; i++) {
		char c[10] = { 0 };
		makeChar(c, i);
		if (!prime[i] && isPelin(c) ){
			printf("%d", i);
			break;
		}
	}
	return 0;
}