2013 코드잼 - Problem C.

Problem C.

3번째 문제다.. 

진자 힘들더라.. 이거참.. 

문제의 규칙은 다음과 같다 

특정 범위의 숫자중 제곱근이면서 팰린드롬의 수인 것을 찾아라.

smaill 과 large input 차이는 어마어마하다.. 10에 몇승인지.. 

처음에는 단순하게 1부터 검사하는 로직을 짰었다. 

smaill은 간단히 패스가 되었지만. large1부턴 난감.. 

어느정도 해결을 보긴 했다. 

요점은 다음과 같다.

규칙 1. 제곱근의 특징은 1,4,5,6,9 로 끝난다.  

규칙 2. 규칙 1을 이용하여 팰린드롬일 가능성은 숫자의 앞 과 뒤는 꼭 1,4,5,6,9 로 시작한다. 

해결책 : 입력 숫자 범위내에서 임의이 순차적으로 숫자를 더해가는 방식이 아닌. 팰린드롬이면서 제곱근일 가능성이 높은 숫자들을 만든다.

하지만 large-1 에서 long 처리를 했을경우 5분 처리가 되서 통과가 되었는데 이를 개선한다고 large-2에서 BigInteger로 바꿨더니 속도가 떨어지더라.. 자바로 이 큰 숫자를 어떻게 처리 해야 할가 참 난감.. 

참고로 숫자 범위 .. ㅋㅋ 

100000200002102004004012042030080030240210400400201200001999901 100000200002102004004012042030080030240210400400201200002000002

뭔지 저거 참.. 

자바로는 속도를 도저히 낼수가 없다.. 

멀티 스레드로 돌려서 처리 해야 하나 싶을 정도.. 

아니면 누가 해결책좀 제시해주셈..ㅠㅠ 

자바로 저걸 어떻게 처리함.. ㅠㅠ 

일단 larg1 -1 까지 처리한 핵심 소스는 다음과 같다. 

입력받은 숫자로부터 다음 팰린드롬이면서 제곱근일 가능성이 있는 수 를 돌려준다. 

/**

* 홀수

* @param c

* @return

*/

private static String odd(BigInteger num) {

//System.out.println("홀수");

StringBuffer sb_temp = new StringBuffer();

StringBuffer sb_mid = new StringBuffer();

StringBuffer sb_final = new StringBuffer();

boolean allNine = true;

char[] ch = num.toString().toCharArray();

int midpos = ch.length / 2;

if(ch[midpos] != '9') {

ch[midpos] = (Character) numberMap.get(ch[midpos]);

sb_final.append(ch);

} else {

//9일때 

ch[midpos] = '0';

if(midpos == 0) //일의 자리에서 10의 자리로 바뀔경우 

{

sb_final.append("11");

}

else //3자리수 이상 

{

//첫자리 추출 

char first = ch[0];

// 두번째 자리부터  중앙 전까지 추출 

for(int i = 1; i < midpos; i++) {

if(ch[i]!='9') allNine = false;

}

//처음 자리수와나머지 자리수가 전부 9면 +1 할것. 

if(first =='9' && allNine) {

sb_temp.append("10");

for(int i =1; i < midpos; i++) {

sb_temp.append("0");

}

sb_final.append(sb_temp);

sb_temp.reverse();

sb_final.append(sb_temp);

} else if(first !='9' && allNine) {

sb_temp.append(squareMap.get(first));

for(int i =1; i < midpos; i++) {

sb_temp.append("0");

}

sb_final.append(sb_temp);

sb_final.append(ch[midpos]);

sb_temp.reverse();

sb_final.append(sb_temp);

} else {

sb_mid.append(first);

for(int i =1; i < midpos; i++) {

sb_mid.append(ch[i]);

}

sb_temp.append(Long.parseLong(sb_mid.toString())+1);

sb_final.append(sb_temp);

sb_final.append(ch[midpos]);

sb_temp.reverse();

sb_final.append(sb_temp);

} 

}

}

return sb_final.toString();

}

/**

* 짝수 

* @param c

* @return

*/

private static String even(BigInteger num) {

//1994  9291   -> 19955991 

StringBuffer sb_temp = new StringBuffer();

StringBuffer sb_mid = new StringBuffer();

StringBuffer sb_final = new StringBuffer();

boolean allNine = true;

char[] ch = num.toString().toCharArray();

int midpos = (ch.length / 2) -1;

//첫자리 추출 

char first = ch[0];

// 두번째 자리부터  중앙 전까지 추출 

for(int i = 1; i <= midpos; i++) {

if(ch[i]!='9') allNine = false;

}

//처음 자리수와나머지 자리수가 전부 9면 +1 할것. 

if(first =='9' && allNine) {

sb_temp.append("10");

for(int i =1; i < ch.length-1; i++) {

sb_temp.append("0");

}

sb_temp.append("1");

sb_final.append(sb_temp);

} else if(first !='9' && allNine) {

sb_temp.append(numberMap.get(first));

for(int i =1; i <= midpos; i++) {

sb_temp.append("0");

}

sb_final.append(sb_temp);

sb_temp.reverse();

sb_final.append(sb_temp);

} else {

sb_mid.append(first);

for(int i =1; i <= midpos; i++) {

sb_mid.append(ch[i]);

}

sb_temp.append(Long.parseLong(sb_mid.toString())+1);

sb_final.append(sb_temp);

sb_temp.reverse();

sb_final.append(sb_temp);

} 

return sb_final.toString();

}

이건 제곱근 검사 

long square =  (long) Math.sqrt(start.longValue());

if (square * square == start.longValue()) {

count++;

}

 

일단 개선 가능성이 있는데 일해야 되므로 난중에 ㄱㄱ