이번 강좌에서는 C#을 활용한 코딩테스트 문제를 다루어보겠습니다.
주제는 “주어진 범위 내의 소수와 팰린드롬 수 중에서 최솟값 찾기”입니다.
이 문제는 알고리즘 사고를 중시하며, 효율적인 코드를 작성하기 위해
다양한 접근 방식을 배울 수 있습니다.
문제 설명
주어진 정수 N에 대해,
1부터 N까지의 정수 중에서 소수이면서
팰린드롬인 수를 모두 찾아 그 중 최솟값을 구하는 문제입니다.
소수란 1과 자기 자신 외에 다른 약수를 가지지 않는 양의 정수를 말하며,
팰린드롬 수란 앞에서 읽으나 뒤에서 읽으나 같은 수를 말합니다.
입력
– 정수 N (1 ≤ N ≤ 1,000,000)
출력
– 소수이면서 팰린드롬 수 중에서 최솟값을 출력하세요.
– 단, 그러한 수가 없을 경우 -1을 출력해야 합니다.
예제 입력
31
예제 출력
11
알고리즘 분석
이 문제를 해결하기 위해서는 다음과 같은 단계로 접근할 수 있습니다:
- 소수 판별: 주어진 범위 내의 수가 소수인지 확인하는 알고리즘을 구현합니다.
- 팰린드롬 판별: 각 수가 팰린드롬인지 확인하는 함수를 작성합니다.
- 최솟값 찾기: 소수이면서 팰린드롬인 수를 모은 후 최솟값을 반환합니다.
C# 코드 구현
아래는 C#을 사용하여 문제를 해결하는 코드입니다.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int N = int.Parse(Console.ReadLine());
int minPrimePalindrome = int.MaxValue;
for (int i = 2; i <= N; i++)
{
if (IsPrime(i) && IsPalindrome(i))
{
minPrimePalindrome = Math.Min(minPrimePalindrome, i);
}
}
Console.WriteLine(minPrimePalindrome == int.MaxValue ? -1 : minPrimePalindrome);
}
static bool IsPrime(int number)
{
if (number < 2) return false;
for (int i = 2; i <= Math.Sqrt(number); i++)
{
if (number % i == 0) return false;
}
return true;
}
static bool IsPalindrome(int number)
{
string str = number.ToString();
int len = str.Length;
for (int i = 0; i < len / 2; i++)
{
if (str[i] != str[len - 1 - i]) return false;
}
return true;
}
}
코드 설명
1. Main 메서드: 입력받은 정수 N에 대해 2부터 N까지의 수를 반복합니다.
각 수가 소수이면서 팰린드롬인지 확인하고, 그 중 최솟값을 찾습니다.
2. IsPrime 메서드: 주어진 수가 소수인지 판단합니다.
2보다 작은 경우는 소수가 아니므로 false를 반환하고,
2부터 √number까지 나누어 떨어지는 수가 있는지를 검사하여 소수 여부를 결정합니다.
3. IsPalindrome 메서드: 주어진 수를 문자열로 변환 후,
앞과 뒤에서부터 비교하여 팰린드롬 여부를 확인합니다.
모든 문자가 일치하면 true를 반환합니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(N√N)입니다.
N까지의 수를 검사할 때, 각 수에 대해 소수 판별에 O(√N)의 시간이 소요되기 때문입니다.
따라서 입력의 범위가 커질수록 연산 시간이 영향을 받으므로,
이점에 유의하여 코드를 작성해야 합니다.
결론
이번 강좌에서 다룬 문제를 통해 소수를 판별하고 팰린드롬을 확인하는 방법을 익혔습니다.
알고리즘 문제를 해결하는 데 있어 소수와 팰린드롬에 대한 이해는
코딩테스트에서 자주 나오는 주제이므로, 잘 연습해 두시기를 바랍니다.
추가적으로 다양한 연습 문제를 통해 실력을 쌓아가시는 것을 추천드립니다.