백준 11068 회문인 수 (JAVA 자바 풀이)

백준 11068 회문인 수 (JAVA 자바 풀이)

 

---

 

 

---

 

 

 

💡 코드 구현

 

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		int testCases = Integer.parseInt(bufferedReader.readLine());
		while (testCases-- > 0) {
			boolean palindromic = false;
			int number = Integer.parseInt(bufferedReader.readLine());
			for (int base = 2; base <= 64; base++) {
				if (isPalindromicNumber(convertToBaseSystem(number, base))) {
					System.out.println("1");
					palindromic = true;
					break;
				}
			}

			if (!palindromic) {
				System.out.println("0");
			}
		}
	}

	private static String convertToBaseSystem(int number, int base) {
		StringBuilder answer = new StringBuilder();
		while (number > 0) {
			int remainder = number % base;
			if (remainder < 10) {
				answer.append(remainder);
			} else {
				answer.append((char)('A' + remainder - 10));
			}
			number /= base;
		}
		return answer.toString();
	}

	private static boolean isPalindromicNumber(int number) {
		return isPalindromicNumber(String.valueOf(number));
	}

	private static boolean isPalindromicNumber(String number) {
		return new StringBuilder(number).toString().equals(new StringBuilder(number).reverse().toString());
	}
}

 

이 문제는 두 가지 로직을 구현할 수 있으면 쉽게 풀리는 문제이다. 

1) 진법 변환 하기

2) 회문 여부 판별하기

 

 

회문 여부를 판별하는 것은 stringbuilder를 사용하면 이와 같이 어렵지 않게 구할 수 있다. 

 

private static boolean isPalindromicNumber(int number) {
   return isPalindromicNumber(String.valueOf(number));
}

private static boolean isPalindromicNumber(String number) {
   return new StringBuilder(number).toString().equals(new StringBuilder(number).reverse().toString());
}

 

진법 변환은 직접 구현을 해주었고 다음과 같은 코드로 작성하였다. 

 

	private static String convertToBaseSystem(int number, int base) {
		StringBuilder answer = new StringBuilder();
		while (number > 0) {
			int remainder = number % base;
			if (remainder < 10) {
				answer.append(remainder);
			} else {
				answer.append((char)('A' + remainder - 10));
			}
			number /= base;
		}
		return answer.toString();
	}

 

 

 

시간 복잡도를 분석해보면 다음과 같다. 

 

 

i) convertToBaseSystem() - 주어진 숫자를 base 진법으로 변환하는 작업을 수행한다. 주어진 숫자의 자릿수에 비례하여 연산이 수행되므로, 주어진 숫자의 자릿수를 d라고 할 때, 시간 복잡도는 O(d)이다.

ii) isPalindromicNumber() - 주어진 숫자가 회문인지 확인하는 작업을 수행한다. 주어진 숫자의 자릿수에 비례하여 연산이 수행되므로, 주어진 숫자의 자릿수를 d라고 할 때, 시간 복잡도는 O(d)이다.

문제에서 테스트 데이터의 최대 값을 1,000,000으로 설정하고 있으므로 최저 자리수인 2진법을 고려해도 자릿수는 상수 시간으로 판단된다. 

 

따라서, 주요한 반복문의 반복 횟수는 입력된 테스트 케이스 수에 비례하며, 즉 O(testCases)가 된다. 

 

T의 범위는 문제에서 주어지지 않고 있으며, 이런 경우 일반적으로 시간 복잡도가 큰 영향을 미치지 않는 문제라고 해석할 수 있겠다.