[백준][C++] 1747 소수&팰린드롬

1747. 소수&팰린드롬

1747번: 소수&팰린드롬

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

소수 구하기는 에라토스테네스의 체로, 팰린드롬은 int형 변수를 string으로 바꾸어서 각각의 문자를 비교해주었다.

 

에라토스테네스의 체로 입력값 이상의 수들을 모두 소수인지, 아닌지 판별해야했기 때문이다. 한계값1 <= N <= 1000000이 확실한 조건을 이용해서 길이가 1000001인 bool형 배열을 만들고, 완전 탐색으로 소수를 찾았다.

 

라는 생각은 좋았지만... 문제는 1000000이상인 소수 & 팰린드롬을 충족해야했기 때문에 소수를 배열의 길이가 1000001으로 부족했던 것!

 

그래서 배열의 길이를 임의로 늘리고 한계값을 넣어본 결과...

1003001이 나온 것이다. 그래서 배열의 길이는 1003002가 되었다.

#define LIMIT 1003001
bool check[LIMIT + 1];

 

회문 판별은 앞에서 말했듯이 int형 변수를 string으로 바꾸어서 했다. 그렇게 하는 편이 구성된 문자 하나하나를 접근할 수 있어서 편하다고 생각했기 때문!

회문인지 아닌지 판별하는 함수

bool IsPalindrome(int number)
{
    string str = to_string(number);

    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] != str[str.size() - i - 1])
        {
            return false;
        }
    }

    return true;
}

 

전체 코드

#include<iostream>
#include<math.h>
#include<string>
#include<string.h>
using namespace std;

#define LIMIT 1003001
bool check[LIMIT + 1];

bool IsPalindrome(int number);

int main()
{
	int number;
	cin >> number;

	memset(&check, true, sizeof(check));

	// ¿¡¶óÅ佺Å׳׽ºÀÇ Ã¼
	for (int i = 2; i <= sqrt(LIMIT); i++)
	{
		if (check[i])
		{
			for (int j = i * i; j <= LIMIT; j += i)
			{
				if (check[j])
				{
					check[j] = false;
				}
			}
		}
	}

	check[1] = false;

	while (true)
	{
		if (check[number] && IsPalindrome(number))
		{
			cout << number;
			return 0;
		}

		number++;
	}
}

bool IsPalindrome(int number)
{
	string str = to_string(number);

	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] != str[str.size() - i - 1])
		{
			return false;
		}
	}

	return true;
}

 

간단하고 재미있었던 문제!