Rebi라는 회사 블로그에서 본 면접문제입니다.

geneven의 이미지

1부터 부터 1억 사이의 palindrome이 몇개인지 세는 알고리즘을 말해보세요. 상식적인 수준의 컴퓨터에서 1초 이내에 결과가 나와야 합니다.

1부터 1억까지 조사하는건데 1초 안에 결과가 나와야 한다면 단순Loop가지고는 안될꺼같고, Loop없이도 조사가 가능할까요?

쿠크다스의 이미지

1억은 palindrome이 아니므로, 제외하고,
그러면, 1-99999999까지.
9가 아홉개네요.

palindrome이 홀수개인 경우는, A(0-9중하나)A를뒤집은것. (1)
palindrome이 짝수개인 경우는, AA를뒤집은것. (2)
위 두 케이스 모두 A는 네자리수이하.

아... 모르겠네요...

과자가 아닙니다.
cuckoo dozen, 즉.12마리의 뻐꾸기란 뜻입니다.

과자가 아닙니다.
cuckoo dozen, 즉.12마리의 뻐꾸기란 뜻입니다.

redneval의 이미지

힌트만 드리자면 '중복순열'

--------------------Signature--------------------
Light a candle before cursing the darkness.

cwryu의 이미지

문제 의도는 알겠는데, 알고리즘 만들다가 사람 머리에서 먼저 답이 나오겠군요...

1자리면 9개, 2자리면 9+9개, 3자리면 9+9+90, 4자리면 9+9+90+90개, ...

select99의 이미지

흠 그냥 생각해보니..
숫자를 반접어 뒤집을수 있고..
마지막 자리가 0을 제외하는경우를 생각하면 결국 한자리 작은 숫자와 동일한가지수일것이기때문에..

각자리숫자의 경우의수를 생각해보니..
9999 - 999
9999 - 999
999 - 99
999 - 99
99 - 9
99 - 9
9
9
-------------------------
9999 + 9999
=19998

이렇게 될거 같네요.. 다더하면 19998 일꺼 같은데.. 맞는지?

select99의 이미지

#include <stdlib.h>
#include <math.h>
int main( int argc, char **argv )
{
        int x;
        if( argc < 2 ) return 0;
        x = atoi( argv[1] );
        printf( "palindrome=%.0f\n", pow( 10, (x+1)/2 )-1 + pow( 10, x/2 )-1);
        return 0;
}
geneven의 이미지

이렇게 생각할수도 있는거였군요. 저는 왜 이걸 Loop을 돌려서 할까라고 생각했습니다.

한자리수의 경우는 0부터 9까지니까 10개가 되는게 맞는건가요?

select99의 이미지

1부터라고 하셨기에 ...

vincenthanna의 이미지

처음에는 1부터 1억까지 루프를돌리면 될까 생각했는데 도저히 1초 안으로 안될것 같아서 생각하다 보니, 순서대로 수를 검사하지 말고 반대로 1억보다 작은 palindrome을 만드는 식으로 풀어가면 되겠구나 하는 생각이 들었습니다.

palindrome의 대칭적인 성격을 이용하여 c로 작성해 보니,

int main(int argc , char** argv)
{
int i = 0;
int count = 0;

for(i = 1 ; i < 9 ; i++) //1자리수부터 8자리수까지(0~99999999)
{
if( (i % 2) ==0 ) //중심수가 없다.
count += (int)(pow((double)10,(double)(i/2)) - 1 ); //ABCD이면 CD는 BA이면 되므로
else //중심수가 있다.
count += (int)( (pow((double)10,(double)(i/2)) -1 ) * 10 ); //ABCDE이면 DE는 BA가 되야하고 C는 0부터 9까지이면 됨
}
count = count - 1; //for문 else에 0도 세어져서 빼야함
printf("number of palindrome : %d\n" , count);

return 0;
}

이렇게 작성해서 돌려보니 22175가 나오는데, 맞는지요?

select99의 이미지

간과한게 있는거 같군요..
제가 위에도 적었듯이.. 반접어 포갤때.. 마지막자리가 0이면 안되겠죠..
즉 반접은수가 9990(1의자리0) 같은수는 자리수자체가 달라지기때문입니다.

suapapa의 이미지

1~99999999(9가 여덟개)
앞서 댓글 달아주신 분들 덕에 쉽게 풀 수 있었습니다. ^^

>>> palindromeCnt = 0
 
#1자리일때 
#1~9까지 9개의 경우의 수가 있습니다.
>>> palindromeCnt += 9 
 
#자리수가 짝수일때
#9 * 10^(자리수/2 - 1)개 만큼의 경우의 수.
#10^(자리수/2)가 아닌 이유는 select99님이 알려주셨네요.
>>> for i in [2,4,6,8]:
	palindromeCnt += (9*(10**(i/2-1)))
 
#자리수가 홀수일때	
#9 * 10^(자리수/2)개 만큼의 경우의 수.
>>> for i in [3,5,7]:
	palindromeCnt += (9*(10**(i/2)))
 
>>> palindromeCnt 
19998
시지프스의 이미지

삭제

댓글 첨부 파일: 
첨부파일 크기
Image icon 83672f25705095b62e54f0aec19615ae.png3.38 KB

begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}