안녕하세요, 김현지입니다.
오늘부터 다시 알고리즘을 시작해보려고 하는데요!
1일 1알고리즘을 Leet Code라는 사이트에서 진행할 예정입니다.
Leet Code는 외국의 프로그래머스 같은 사이트라고 할 수 있을 것 같습니다.
저는 사이트에서 진행하는 한 달간 매일 올라오는 알고리즘을 푸는 챌린지인 LeetCoding Challenge를 뒤늦게나마 도전하려고 합니다 :)
오늘은 Super Palindromes을 풀어봤습니다.
문제
요약
palindrom 은 쉽게 말해서 ' 앞뒤가 똑같은 단어 ' 입니다.
문제는 left <= num < right 의 범위에서 num 과 num의 제곱근 모두가 palindrom 인 숫자의 개수를 찾아서 return하는 문제입니다.
처음 시도한 방법
무작정
left부터right까지 for문을 순회하면서 풀었습니다.
테스트 케이스는 통과했지만 범위가 굉장히 컸기 때문에 time 에러를 마주했습니다.
두번째로 시도한 방법
left와right의 제곱근을 구해서 올림을 한 다음에 그 사이의 범위에서palindrom을 찾고, 만약 해당 숫자가palindrom이면 그것의 제곱도palindrom인지 검사하는 알고리즘으로 바꾸었습니다.
그래도.. time 에러가 발생하더라고요..
대략 1시간이 넘는 시간동안 생각하다가 도저히 안되겠어서! Solution을 보고 참고해서 풀었습니다 :)
코드 설명
우선 right 의 길이가 18이면 그것의 제곱근은 길이가 9가 될 것입니다.
그 제곱근도 너무 범위가 길기 때문에, 여기서 palindrom 의 특징을 반영합니다.
palindrom 의 특징은 바로 ' 앞에서 읽은 것과 뒤에서 읽은 것이 같다 ' 라는 것이겠죠.
그렇기 때문에 길이를 또 반으로 줄일 수 있습니다.
WHY?
123454321에서12345까지만 구한 후에 뒷 부분에4321을 더해서palindrom검사를 하겠다는 원리입니다.
그래서 for문의 범위는int MAX = 100000;가 되는 것입니다.
또한,palindrom은 길이가 짝수일 경우와 홀수일 경우가 나누어집니다.
그래서 for문을 짝수일 경우와 홀수일 경우 두 번 순회합니다.
변수 선언
int count = 0; // palindrom 개수
long leftNum = Long.parseLong(left); // left 범위
long rightNum = Long.parseLong(right); // right 범위
int MAX = 100000; // for문 범위palindrom 의 길이가 홀수인 경우
for (int i = 1; i < MAX; ++i) {
StringBuilder sb = new StringBuilder(Integer.toString(i));
for (int j = sb.length() - 2; j >= 0; --j) {
sb.append(sb.charAt(j));
}
long num = Long.parseLong(sb.toString());
num *= num;
if (num > rightNum) break;
if (num >= leftNum && isPalindrom(num)) count++;
}제가 알고리즘을 해결할 때 사용하는 언어인 Java 는 String 을 활용할 때 속도가 현저히 느려지기 때문에, StringBuilder 를 사용했습니다.
길이가 홀수이기 때문에 palindrom의 반을 의미하는 sb 뒤를 이어붙이는 for문에서 j 가 sb.length() - 2 부터 시작하는 부분을 주의하셔야 합니다.
ex) 12345 -> 123454321 가 되기 위해서는 4321 이 필요하다.
그리고 String 으로 palindrom 검사를 진행하면 그것 또한 시간이 오래 소요되기 때문에 long 타입으로 진행합니다.
palindrom 의 길이가 짝수인 경우
for (int i = 1; i < MAX; ++i) {
StringBuilder sb = new StringBuilder(Integer.toString(i));
for (int j = sb.length() - 1; j >= 0; --j) {
sb.append(sb.charAt(j));
}
long num = Long.parseLong(sb.toString());
num *= num;
if (num > rightNum) break;
if (num >= leftNum && isPalindrom(num)) count++;
}길이가 홀수일 경우와 비슷하지만, 내부 for문에서 j 가 sb.length() - 1 부터 시작한다는 부분을 주의하셔야 합니다.
isPalindrom 메서드
private boolean isPalindrom(long num) {
return num == reverse(num);
}reverse 메서드
private long reverse(long num) {
long result = 0;
while (num > 0) {
result = 10 * result + num % 10;
num /= 10;
}
return result;
}위의 두 메서드를 사용해서 palindrom 검사를 진행합니다.
전체 코드
class Solution {
public int superpalindromesInRange(String left, String right) {
int count = 0;
long leftNum = Long.parseLong(left);
long rightNum = Long.parseLong(right);
int MAX = 100000;
// 길이가 홀수인 palindrom
for (int i = 1; i < MAX; ++i) {
StringBuilder sb = new StringBuilder(Integer.toString(i));
for (int j = sb.length() - 2; j >= 0; --j) {
sb.append(sb.charAt(j));
}
long num = Long.parseLong(sb.toString());
num *= num;
if (num > rightNum) break;
if (num >= leftNum && isPalindrom(num)) count++;
}
// 길이가 짝수인 palindrom
for (int i = 1; i < MAX; ++i) {
StringBuilder sb = new StringBuilder(Integer.toString(i));
for (int j = sb.length() - 1; j >= 0; --j) {
sb.append(sb.charAt(j));
}
long num = Long.parseLong(sb.toString());
num *= num;
if (num > rightNum) break;
if (num >= leftNum && isPalindrom(num)) count++;
}
return count;
}
private boolean isPalindrom(long num) {
return num == reverse(num);
}
private long reverse(long num) {
long result = 0;
while (num > 0) {
result = 10 * result + num % 10;
num /= 10;
}
return result;
}
}마무리
palindrom 검사를 숫자 타입으로 진행한 것은 처음인데, 새로운 알고리즘을 알게된 것 같은 느낌을 받은 문제였습니다.
내일은 Solution 참고 안하고 풀 수 있도록 노력해보겠습니다 :)
