92일 (2396. Strictly Palindromic Number) Two pointers, String

An integer n is strictly palindromic if, for every base b between 2 and n - 2 (inclusive), the string representation of the integer n in base b is palindromic.

Given an integer n, return true if n is strictly palindromic and false otherwise.

A string is palindromic if it reads the same forward and backward.

 

Example 1:

Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.

Example 2:

Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.

 

Constraints:

• 4 <= n <= 10^5

 

- 접근방법

0. n이 존재할때, 2 ~ n-1진법으로 표현된 모든 n이 회문인 경우만 n은 Strictly Palindromic Number이고 true이다.

모든 진법(base)을 표현하는 함수를 만들어서 쓰면 좋을 것이다.

 

 

1. 투 포인터와 곱셈으로 회문판별 : N진법 3자리 숫자가 존재할때, base^0, base^1, base^2 각각 자릿수 일의자리, 십의자리 백의자리로 올리면서 자릿수를 구성하는 수는 백의자리, 십의자리, 일의자리 역순으로 센 후 곱한다. 이 경우 기존의 수와 같다면 회문.

 

2. StringBuilder 이용 :reverse()는 문자열을 뒤집을 수 있어서 회문을 판별할 때 강력한 기능이라고 생각한다.

 

 

 

- 코드 (1. 투 포인터)

class Solution {
    public boolean isStrictlyPalindromic(int n) {

        for(int i = 2; i < n-1; i++) {
            if(!isPalindromic(n,i)) return false;
        }

        return true;
    }

    private boolean isPalindromic (int n, int base) { // 투 포인터
        int ptr1 = 0;
        int ptr2 = n;

        while(n > 0) {
            ptr1 = (ptr1 * base) + (n % base); 
            n /= base;
        }
		
        // 예를들어 11 == 11, 91 != 19
        return ptr1 == ptr2;
    }
}

 

 

 

- 코드 (2. StirngBuilder 이용)

class Solution {
    public boolean isStrictlyPalindromic(int n) {

        for(int i = 2; i < n-1; i++) {
            StringBuilder stringBuilder = new StringBuilder();
            
            while(n > 0) { // n을 i진법으로 표현, 회문판별이니 append()로 역순저장도 가능
                stringBuilder.insert(0,n%i);
                n /= i;
            }
            
            // i진법으로 표현된 n이 회문인지
            if(stringBuilder.toString() != stringBuilder.reverse().toString()) return false;
        }

        return true;
    }
}

 

 

이 문제도 기가막히게 역따봉이 많은 이유가

투포인터가 이 문제의 키워드였는데 오히려 StringBuilder를 사용하는게 공간복잡도를 더욱 더 줄일 수 있었기 때문이다.

 

그리고 공간복잡도를 극한으로 줄였음에도 불구하고 하위10퍼센트로 통과되어서 원인을 찾아보았는데

이러한 이유는 단지 return false를 제출하여도 모든 테스트케이스가 통과되는 어처구니 경우 때문이었다.

 

 

 

https://leetcode.com/problems/strictly-palindromic-number/

Strictly Palindromic Number - LeetCode