링크
https://www.acmicpc.net/problem/1747
문제 설명
정답률 30.688%
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
입력 예제
- 첫째 줄에 N이 주어진다.
31
출력 예제
- 첫째 줄에 조건을 만족하는 수를 출력한다.
101
풀이
소수와 팰린드롬 여부를 동시에 판단하는 문제이다. 우선 에라토스테네스의 체를 이용해 소수를 판별한다.
static final int MAX = 10_000_001;
static boolean[] isPrime = new boolean[MAX];
static void sieveOfEratosthenes() {
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < MAX; i++) {
if (isPrime[i]) {
for (int j = i * i; j < MAX; j += i) {
isPrime[j] = false;
}
}
}
}그리고 수의 대칭 여부를 판단하기 위해 투 포인터를 이용한다.
static boolean isPalindrome(int number) {
char[] charArray = String.valueOf(number).toCharArray();
String[] split = String.valueOf(number).split("");
int s = 0;
int e = split.length - 1;
while (s < e) {
//대칭이 깨질 경우 false
if (!split[s].equals(split[e])) {
return false;
}
s++;
e--;
}
return true;
}이제 수를 증가시켜가며 N보다 크거나 같은 수에 대해 판별을 한다.
while (true) {
if (isPrime[N] && isPalindrome(N)) {
System.out.println(N);
break;
}
N++;
}코드
//백준
public class Main {
static final int MAX = 10_000_001;
static boolean[] isPrime = new boolean[MAX];
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //10^6
sieveOfEratosthenes();
while (true) {
if (isPrime[N] && isPalindrome(N)) {
System.out.println(N);
break;
}
N++;
}
}
static boolean isPalindrome(int number) {
String[] split = String.valueOf(number).split("");
int s = 0;
int e = split.length - 1;
while (s < e) {
if (!split[s].equals(split[e])) {
return false;
}
s++;
e--;
}
return true;
}
static void sieveOfEratosthenes() {
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < MAX; i++) {
if (isPrime[i]) {
for (int j = i * i; j < MAX; j += i) {
isPrime[j] = false;
}
}
}
}
}참고
팰린드롬인 수를 찾는 과정에서 String 배열을 이용했는데 char 배열으로만 바꿨을 뿐인데 성능 차이가 꽤 많이 났다.
검색을 해본 결과 다음과 같은 이유가 있었다.
아무래도 string은 편리성을 위해 메모리의 동적 할당이나 문자열의 길이 정보 등을 같이 들고 다니기 때문에 char 배열을 직접적으로 쓰는 것에 비해서는 약간의 오버헤드가 있을 수 있기는 하지만, 그 차이는 매우 미미하기 때문에 대부분의 경우 무시할 수 있을 수준입니다. 그 차이가 비해 string이 주는 편리함은 비교할 수 없을 정도로 크기 때문에 웬만하면 그냥 string을 쓰는 것을 추천합니다.
만약에 어떤 문제를 푸는데 char로는 여유있게 통과되는데 string으로는 통과가 안 된다면 그건 단순히 둘의 속도 차이가 많이 나서가 아니라 애초에 string으로 풀 때 시간 복잡도상 비효율적인 코드를 작성했기 때문일 가능성이 높습니다.
그러므로 굳이 char 배열을 쓸 필요는 없을거 같다.
