[백준] 1747번: 소수&팰린드롬 - Java, Python

처음 파이썬으로 문제를 풀었을 때 채점 시간이 엄청 오래 걸리더니 결국 시간초과가 나버렸다. 언제나처럼 이중 for문을 사용한 것이 문제였고 문제를 해결한 다른 블로그를 참조하여 코드를 작성하였다. 이중 for문이 쉽고 좋은데.. 시간이 너무 오래 걸려서 슬프다. 이전까지는 이중 for문이 만능이었는데 시간복잡도나 자료구조, 알고리즘을 배우고 코드를 작성해보니 최악이라는 생각이 들기도 한다. 더 열심히 대응방안을 찾아봐야겠다. 

 

 

---

처음에 작성했던 코드 (시간 초과)

import sys
N = int(sys.stdin.readline()) # 수 입력받기

a = [2]

for i in range(N, 1000000000000): # while문 대신 for문을 사용
    x = 1
    
    for j in range(2, i): # 소수가 아니라면 바로 break
        if i % j == 0:
            x = 0
            break

    if x == 1: # 소수라면 팰린드롬 수인지 확인
        err = str(i)
        err = list(err)
        err.reverse()
        err = ''.join(err) # 기존의 수를 뒤집어서

        if err == str(i): # 두 수가 동일하면 break하고 출력
            a.append(i)
            break
        

print(max(a))

 

소수를 확인하는 것도, 팰린드롬을 확인하는 것도 굉장히 복잡하고 시간이 오래 걸린다. 다른 사람들의 블로그를 참조했을 때 우선 소수 구하는 방법부터 확인했다. 모두 에라토스테네스의 체를 활용하여 처음부터 끝까지 2부터 N까지 소수 여부를 체크하는 것이 아닌 2부터 N의 제곱근까지만 체크하였다. 이에 따라 함수도 작성하여 수정하니 통과할 수 있었다.

 

---

수정한 코드

import sys
import math

N = int(sys.stdin.readline())

def isPrime(N): # 소수 여부 판별
    if N == 1:
        return False
    for i in range(2, int(math.sqrt(N) + 1)): # 에라토스테네스의 체 활용
        if N % i == 0:
            return False
    return True


def isPalindrome(N): # 팰린드롬수 여부 판별
    if str(N) == str(N)[::-1] # 역수와 비교
        return True
    return False
    
    
while True: # 소수이고 팰린드롬수인 경우 출력 후 break
    if isPrime(N) and isPalindrome(N):
        print(N)
        break
    N += 1

 

---

 

Java 코드

import java.io.*;
import java.util.*;
import java.lang.StringBuffer;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 값 입력받기
        String x = br.readLine();
        int N = Integer.parseInt(x);

		// 소수이고 팰린드롬수이면 값을 출력 후 break
        while(true){
            if(isPrime(N) & isPalindrome(N)){
                System.out.println(N);
                break;
            }
            N++;
        }
    }

	// 소수 여부 체크
    public static boolean isPrime(int n){
        if(n == 1)
            return false;

 		// 에라토스테네스의 체 활용
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
	
    // 팰린드롬수 여부 체크
    public static boolean isPalindrome(int n){
        String N = String.valueOf(n);
        StringBuilder sb = new StringBuilder(N);
        String rev = sb.reverse().toString(); // 입력 받은 문자열 뒤집기

		// 팰린드롬 수이면 true를 return
        if((n+"").equals(rev)){
            return true;
        }
        return false;
    }
}

python으로 코드를 짜서 통과를 한 후 항상 java로 문제를 다시 푸는데 python과는 달리 복잡한 부분이 있었다. 

파이썬은 문자열을 거꾸로 만들기 위해 [::-1] 코드만 작성하면 됐는데 

자바는 처음보는 StringBuilder를 사용해서 뒤집어야 했다.

자바로 코드를 짜면서 파이썬의 소중함을 항상 느끼게 된다.

 

문제 하나에 다양한 언어, 알고리즘, 방식으로 풀 수 있다는 사실이 신기했다.

그리고 인턴으로 일하며 데이터의 규격, 폴더, 파일명등이 잦은 회의때마다 수정되어 알아보기 쉽고 수정이 용이한 코드 작성의 중요성을 크게 체감하였다. 코딩테스트도 포함하여 앞으로 코드를 작성할 때 한눈에 알아볼 수 있고 간편하게 수정할 수 있는 코드를 작성해야겠다. 

백준 문제를 풀며 골드로 등급을 빨리 올리고 싶다는 생각도 했다. 아직 브론즈나 실버 문제 밖에 풀어보지 못했지만 골드도 손 쉽게 푸는 실력이 되어 골드도 찍고 골드 문제도 푸는 고수가 되고싶다. 🍀