[Algorithm] SWEA. 10570 제곱 팰린드롬 수 ( D3 )

[SWEA] 10570. 제곱 팰린드롬 수

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXO72aaqPrcDFAXS&categoryId=AXO72aaqPrcDFAXS&categoryType=CODE

SW Expert Academy

 

팰린드롬이란?

거꾸로 읽어도 동일한 문자(숫자)를 말한다.

 

보통 문자열의 절반까지 반복문 돌려 n번째 문자와 문자길이 - n 번째 문자를 비교하는 방식으로 검증한다.

 

[ 접근방식 ] 

값의 범위가 1~1000이므로 31의 제곱수 까지 확인하면 모두 체크가 가능하다고 생각하여 테스트 케이스 마다 연산하지 않고 팰린드롬 여부를 판단하는 배열을 생성하였다 .

boolean 타입으로 32개 짜리 배열을 선언하고 각 수와 제곱 수가 팰린드롬이라면 true값으로 지정하였다.

 

테스트 케이스마다 주어지는 두 숫자를 Math.ceil(number)과 Math.floor(number)을 이용해 제곱할 값의 범위를 설정하였고, 숫자를 문자열로 변환하여 String.charAt(n)함수를 이용해 n번째 숫자와 (문자길이 - 1 - n)번째의 숫자가 모두 일치하면 팰린드롬이라고 판단하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		boolean[] isPalendrome = new boolean[32];
		for (int i = 1; i < 32; i++) {
			if (check(i) && check((int)Math.pow(i, 2))) {
				isPalendrome[i] = true;
			}
		}
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int res = 0;
			int start = (int)Math.ceil(Math.sqrt(Integer.parseInt(st.nextToken())));
			int end = (int)Math.floor(Math.sqrt(Integer.parseInt(st.nextToken())));
			for(int i = start; i <= end ; i++) {
				if(isPalendrome[i])
					res++;
			}
			System.out.println("#" + t + " " + res);
		}
	}

	private static boolean check(int num) {
		String s_num = num + "";
		int cnt = 0;
		while (cnt < s_num.length() / 2) {
			if (s_num.charAt(cnt) != s_num.charAt(s_num.length() - cnt-1))
				return false;
			cnt++;
		}

		return true;
	}
}