코테/백준
[백준/JAVA] 1747번: 소수&팰린드롬
imname1am
2023. 4. 25. 17:50
반응형
🔺 문제
1747번: 소수&팰린드롬
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고,
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] A = new int[10000001];
// 소수 판정
// 배열 초기화
for(int i = 2 ; i < A.length ; i++) {
A[i] = i;
}
for(int i = 2 ; i < A.length ; i++) {
if(A[i] == 0) {
continue;
}
// 배수 지우기
for(int j = i+i ; j < A.length ; j += i) {
A[j] = 0;
}
}
StringBuilder sb = new StringBuilder();
for(int i = N ; ; i++) {
if(A[i] != 0 && isPalindrome(A[i])) {
sb.append(A[i]);
break;
}
}
System.out.println(sb);
}
// 팰린드롬 판별 함수
static boolean isPalindrome(int num) {
String str = Integer.toString(num);
int len = str.length();
for(int i = 0 ; i < len / 2 ; i++) {
if(str.charAt(i) != str.charAt(len - 1 - i)) {
return false;
}
}
return true;
}
}
|
cs |
✅ 해결 아이디어
✔ 소수 판정 - 에라토스테네스의 체
✔ 팰린드롬 판별 - 투포인터
🔺 다른 풀이들
- while문 사용 & isPalindrome에서 char형으로 받아서 사용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] A = new int[10000001];
for(int i = 2 ; i < A.length ; i++) {
A[i] = i;
}
for(int i = 2 ; i < A.length ; i++) {
if(A[i] == 0) {
continue;
}
for(int j = i+i ; j < A.length ; j += i) {
A[j] = 0;
}
}
StringBuilder sb = new StringBuilder();
int i = N;
while(true) {
if(A[i] != 0 && isPalindrome(A[i])) {
sb.append(A[i]);
break;
}
i++;
}
System.out.println(sb);
}
static boolean isPalindrome(int num) {
char tmp[] = String.valueOf(num).toCharArray();
int s = 0;
int e = tmp.length - 1;
while(s < e) {
if(tmp[s] != tmp[e])
return false;
s++;
e--;
}
return true;
}
}
|
cs |
- 팰린드롬 → StringBuilder의 reverse() 메소드 사용
[1747] 백준 - 소수&팰린드롬(JAVA)
[ 풀이 방법 ] - N부터 충분히 큰 수 사이에서, 소수이면서 팰린드롬인 숫자를 찾으면 출력하고 종료 - 소수 찾기 => 에라토스테네스의 체 - 팰린드롬 => StringBuilder를 이용하여 문자열을 뒤집은 것
jisunshine.tistory.com
💬 느낀 점
핫시... 자꾸 런타임 에러 (ArrayIndexOutOfBounds) 떠서 뭐지..하고 정답 코드 보니까
배열 크기 작성할 때 0을 6개 넣어야 하는데 5개 넣어서였음,,,,,
이것 땜에 20분 삽질했는뎁쇼,,,
암튼 혼자 풀었으니 뿌듯하다!!!
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 6/20 |
(+ 6/20 2회독)
마지막에 StringBuilder 만든 값과 reverse한 값 비교할 때 어쩌지..하다가 조금 헤맸다.
sb.toString().equals(sb.reverse().toString()) 로 하면 된다.
그리고 소수 판별 처리 함수에서 1일 때도 놓치면 안 됨...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(br.readLine());
long answer = 0;
for(int i = (int)N ; ; i++) {
if(isPrime(i) && isPalindrome(i)) {
answer = i;
break;
}
}
System.out.println(answer);
}
// 소수 판별 함수
static boolean isPrime(int n) {
if(n == 1) {
return false;
}
for(int i = 2 ; i <= (int)Math.sqrt(n) ; i++) {
if(n % i == 0) {
return false;
}
}
return true;
}
// 팰린드롬 판별 함수
static boolean isPalindrome(int n) {
StringBuilder sb = new StringBuilder(Integer.toString(n));
if(sb.toString().equals(sb.reverse().toString())) {
return true;
}
return false;
}
}
|
cs |
반응형