앞뒤가 같은 수는 바로 쓴 값과 거꾸로 쓴 값이 같은 수이다. 다음과 같은 예를 들 수 있다.
1
44
101
2002
8972798
1111111111111
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, ... 과 같이, 0 이상의 앞뒤가 같은 수를 크기 순으로 나열할 때, n 번째 수를 계산하는 프로그램을 작성하라.
n은 1부터 시작하며 크기에는 제한이 없다.
예 1) 1 => 0
예 2) 4 => 3
예 3) 30 => 202
예 4) 100 => 909
예 5) 30000 => 200000002
예 6) 1000000 => 90000000009
181개의 풀이가 있습니다.
foo 방식으로 순차적으로 접근하면 연산이 너무느려서 쓸수가 없습니다.
n자리수의 앞뒤가 같은수를 만드는 함수를 이용해서 bar로 연산하면
빠른속도로 결과를 얻을수 있습니다.
coding by python beginner
def foo(n):
loop = i = 0
while loop < n:
if str(i) == str(i)[::-1]:
loop += 1
i+=1
print(i-1)
# foo(1)
# foo(4)
# foo(30)
# foo(100)
# foo(30000)
# foo(1000000)
def bar(n):
pLen = 1; lenTotal = 0; palindrome = None
while lenTotal < n:
palindromes = getPalindromes(pLen)
lenTotal += len(palindromes)
pLen += 1
print(palindromes[n - (lenTotal+1)])
def getPalindromes(l):
if l < 1: return []
if l == 1: return [x for x in range(10)]
palindromes = []
if l % 2 == 0:
halfLen = l // 2
for i in range(10 ** (halfLen - 1), 10 ** halfLen):
palindromes.append(int(str(i) + str(i)[::-1]))
else:
halfLen = (l-1) // 2
for i in range(0, 10):
for j in range(10 ** (halfLen - 1), 10 ** halfLen):
palindromes.append(int(str(j) + str(i) + str(j)[::-1]))
palindromes.sort()
return palindromes
bar(1)
bar(4)
bar(30)
bar(100)
bar(30000)
bar(1000000)
python 3.7
n = int(input())
a = int(str(n)[:2])
b = 10**(len(str(n))-1)
if 0 < n < 11:
print(n-1)
elif a < 11:
print(str(n-int(b/10))+str(n-int(b/10))[-2::-1])
elif a < 20:
print(str(n-b)+str(n-b)[::-1])
else:
print(str(n-b)+str(n-b)[-2::-1])
// SP_SameNumber.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include "stdafx.h"
#include <math.h>
int GetNum(int nDigit,int& nMin) // 자리수 별로 몇개의 숫자가 있는지 확인
{
int nCount = 1;
if(nDigit == 1)
return 10;
if(nDigit == 2)
return 9;
nDigit = (nDigit+1)/2 ;
nMin = pow(10.0,nDigit-1);
nCount = pow(10.0,nDigit) - nMin;
return nCount;
}
int _tmain(int argc, _TCHAR* argv[])
{
while(1)
{
int nNum = 0;
printf("?");
scanf("%d",&nNum);
int nNumber = 0;
int nOldNum = nNum-1;
if(nOldNum >= 10 && nOldNum < 19)
{
nOldNum ++;
}
int nDigit = 1;
if(nNum<=0)
break;
while(1)
{
int nMin = 0;
int nCount = GetNum(nDigit,nMin);
nNumber += nCount;
if(nNumber >=nNum)
{
nOldNum +=nMin;
char chOut[32];
char* p = chOut;
sprintf(chOut,"%d",nOldNum,nOldNum%(int)pow(10.0,(int)(nDigit/2)));
int nLen = printf(chOut);
p+= nLen;
if(nDigit%2)
p--;
while(--p >= chOut)
printf("%c", *p);
break;
}
nDigit++;
nOldNum -= nCount;
}
}
return 0;
}
계산 으로 하는 거라 광속 입니다.
Python 3.4 기준 입니다. n 이 커지면 느려지는게 눈에 띄네요. 속도를 높이려면 어떻게 해야할 지 잘 모르겠습니다.
count = int(input())
pal_list=[]
num = 0
def dec_pal(num): #정수가 palindrome 인지 아닌지를 판단하여 리스트에 추가
num_str = str(num)
num_len = len(num_str)
check = 0
for x in range(num_len):
if num_str[x] == num_str[-(x+1)]:
check += 1
else:
break
if check == num_len:
pal_list.append(num)
while len(pal_list) < count: # palindromic number list의 수가 지정한 숫자에 이를 때까지 리스트에 palindrome 추가
dec_pal(num)
num += 1
print(pal_list[-1]) # 맨 마지막 숫자를 읽으면 n번째 palindromic number
import java.util.ArrayList;
import java.util.Scanner;
public class Lv3 {
public void func() {
Scanner sc = new Scanner(System.in);
int input = sc.nextInt();
ArrayList<Integer> arr = new ArrayList<Integer>();
int i = 0;
while (arr.size() < input) {
StringBuffer sb = new StringBuffer(String.valueOf(i));
if (sb.toString().equals(sb.reverse().toString())) arr.add(i++);
else i++;
}
System.out.println(arr.get(input-1));
}
public static void main(String[] args) {
Lv3 obj = new Lv3();
obj.func();
}
}
public class Number{
String number_palindrome(int n) {
int c=18,h;
for (n--;n>c;n-=c,c*=10);
h=c/18 + n -1;
n=n>c/2?h-=c/2:h/10;
String s = ""+ h;
for (;n>0;s+=n%10,n/=10);
return s;
}
public static void main(String[] args){
NumberPalindrome obj = new NumberPalindrome();
int[] numbers = new int[]{1, 4, 30, 100, 30000, 1000000};
for (int k:numbers){
System.out.println("k = " + k + ", k-th palindrome = " + obj.number_palindrome(k));
}
}
}
C로 짯구요 while 문이 두개라서 좀 느리네요 ㅋㅋㅋㅠㅠ sprintf 함수로 간단히 해결은 했습니다
#define SIZE 20
int main()
{
int userInput;
scanf("%d", &userInput);
int i = 0;
char arr[SIZE];
int count = 0;
int save = 0;
while(count != userInput)
{
//정수 문자열로 변환 저장
sprintf( arr, "%d", i );
int start = 0;
int end = strlen(arr) -1;
//같은지 검사
while(1)
{
if( arr[start] == arr[end] )
{
start++; end--;
if( start > end )
{
save = i;
count++;
break;
}
}
else
{
break;
}
}
i++;
}
printf("%d", save);
}
Java로 짜봤어요^^ 어떤가요?;ㅎㅎ
/* 바로쓴값과 거꾸로쓴 값은, 거울처럼 숫자가 거꾸로 다시 반복된다는 데 착안했어요
* 자릿수가 홀수일 경우 마지막 숫자를 제외하고 숫자가 다시 거울처럼 거꾸로 반복되고, ex. 123454321
* 홀수일 경우에는 그냥 다시 거울처럼 반복되요 ex.1234554321
* 반복되는 숫자를 half라고 놓고, 실제 값의 자릿수(l)과 half의 자릿수(lh)를 이용하여 계산했습니다*/
package h14;
import java.util.Scanner;
public class HelloTest {
long m10(int m){ // 함수m10 : 10의 input승 구하기
long result=1;
for(int i=0;i<m;i++) result*=10;
return result;
}
long back(long input){ // 함수 back : 숫자를 거꾸로
HelloTest h=new HelloTest();
long result=0;
int l=0; //l:length 자릿수. 일단 자릿수(l)을 구한다
for(long m=1; input/m!=0 ; m*=10) l++;
if(input==0) l=1;
for(int i=0; i<l; i++) result+=((input/h.m10(i))%10)*h.m10(l-1-i);
return result;
}
public static void main(String[] args) {
HelloTest h=new HelloTest();
Scanner num=new Scanner(System.in);
int n, i, j, l=1, lh=1, n9=0; //l:length 자릿수, lh:length_half
long half=0;
boolean check_odd=true; //자릿수가 홀수개인지 아닌지 여부
n=num.nextInt();//값을 입력받음
long[] arr=new long[n];
for(i=0;i<n;i++){
if(check_odd){ //자릿수가 홀수개이면 : half를 마지막숫자를 제외하고 거울처럼 반복
arr[i]=half*h.m10(lh-1);
arr[i]+=h.back(half/10);
half++;
}
else{ // 자릿수가 짝수개이면 : half를 거울처럼 반복
arr[i]=half*h.m10(lh);
arr[i]+=h.back(half);
half++;
}
//숫자가 9로만 이루어진 수일 경우,
for(n9=0, j=0; j<lh && (half/h.m10(j))%10==9 ; j++) n9++;
if(n9==lh){ // : 일단 arr[++i]에 대입한 후, 자릿수 하나 늘리고 half 재설정
arr[++i]=(check_odd)? half*h.m10(lh-1)+(half/10) : half*h.m10(lh)+half;
check_odd=(!check_odd);
l++; if(check_odd) lh++;
half=h.m10(lh-1);
}
}
System.out.println(arr[--i]);
}
}
python 2.4.3입니다. python 공부중이라서... 소스 정리는 잘 못한듯
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys # argv를 위해서 사용됨.
def usage():
print "usage: python palindrome.py nth-number"
# 인자가 맞지 않는 경우 Usage 출력
if len(sys.argv) - 1 <> 1:
usage()
sys.exit()
nth = int(sys.argv[1])
# case: 1자리 일 때 경우의 수 -> 10
# 2자리 일 때 경우의 수 -> 9 (11,22, ..., 99)
# 3자리 일 때 경우의 수 -> 9 * 10 (101, 111, 121, ..., 191, 202, 212, 222, ..., 292, ..., 999)
# 4자리 일 때 경우의 수 -> 9 * 10 (1001, 1111, 1221, ..., 1991, 2002, 2112, 2222, ... 2992, ..., 9999)
# 5자리 일 때 경우의 수 -> 9 * 10 * 10
# 6자리 일 때 경우의 수 -> 9 * 10 * 10
#
# 일반화 시키면, n자리 일때
# n = 1 일 때 경우의 수 -> 10개
# n = 2 일 때 경우의 수 -> 9개
# n >= 3 일 때 경우의 수 -> 9 * 10^((n-1)/2)
def get_digit_count(nth):
if nth <= 10:
digit_count = 1
elif nth <= 10 + 9:
digit_count = 2
else:
digit_count = 3
acc_num_count = 19
while True:
acc_num_count = acc_num_count + 9 * pow(10, (digit_count-1)/2)
if nth <= acc_num_count:
break
digit_count = digit_count + 1
return digit_count
def get_acc_num_count_of_digit_count(digit_count):
acc_num_count = 0
if digit_count == 0:
acc_num_count = 0
elif digit_count == 1:
acc_num_count = 10
elif digit_count == 2:
acc_num_count = 10 + 9
else:
acc_num_count = 10 + 9
for i in range(3, digit_count + 1):
acc_num_count = acc_num_count + 9 * pow(10, (i-1)/2)
return acc_num_count
def get_nth_number(nth):
digit_count = get_digit_count(nth)
acc_num_count = get_acc_num_count_of_digit_count(digit_count - 1)
d_n = nth - acc_num_count
start_number_prefix = pow(10, (digit_count-1)/2)
if digit_count == 1:
start_number_prefix = 0
nth_number_prefix = start_number_prefix + (d_n - 1)
if digit_count % 2 == 0:
nth_number_prefix = str(nth_number_prefix) + str(nth_number_prefix)[::-1]
else:
nth_number_prefix = str(nth_number_prefix) + str(nth_number_prefix / 10)[::-1]
return nth_number_prefix;
print str(nth) + " => " + get_nth_number(nth)
C# 으로 풀었습니다.
private int GetNum(int nIndex)
{
int nData = nIndex;
int nDigit1 = 1;
int nDigit2 = 1;
int nDigit3 = 1;
int nRealDigit = GetDigit(nIndex);
nDigit1 = (int)Math.Pow(10, nRealDigit);
nData = (nData - nDigit1);
if (nRealDigit > 0)
{
int number2 = (nData * nDigit1);
nDigit2 = (int)Math.Log10(number2) + 1;
if (nDigit2 % 2 == 0)
{
nDigit3 = 1;
}
else
{
nDigit3 = 10;
}
nData = number2 + Reverse(nData / nDigit3);
}
return nData;
}
private int Reverse(int nData)
{
int nResver = 0;
do
{
nResver = (nData % 10) + (nResver * 10);
}
while ((nData /= 10) > 0);
return nResver;
}
private int GetDigit(int nData)
{
int nCount = 0;
while (nData > 10)
{
nData /= 10;
nCount++;
}
return nCount;
}
c#
public class Palindrome
{
public int GetResult(int targetIndex)
{
int trialNumber = 0;
int matchingCount = 0;
while (matchingCount != targetIndex)
{
if (IsPalindrome(trialNumber++))
{
matchingCount++;
}
}
return --trialNumber;
}
private bool IsPalindrome(int value)
{
if (value == 0)
return true;
var stringfied = value.ToString();
var head = stringfied.Take(stringfied.Length / 2);
var tail = stringfied.Skip((stringfied.Length % 2 == 0) ? head.Count() : head.Count() + 1)
.Take(head.Count()).Reverse();
return head.SequenceEqual(tail);
}
}
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=EUC-KR">
<script>
function goCalc(){
var txt = document.getElementById("txtBox").value;
var result = document.getElementById("result");
// 1~10 처리
if(txt-10 < 1){
result.innerText = txt -1;
}else{
//1.입력받은 받은 수의 자릿수를 구한다.
//2.자릿수 -1 의 10의 제곱근을 구한다. n^n-1
//3.입력받은 수를 2번의 수로 나눗셈을 한다.
//4.나눗셈 결과가 2보다 작으면 n - (n^n-2) 를 한다.
//4-1.나눗셈 결과가 2보다 크면 n- (n^n-1) 를 한다.
var txtLen = txt.toString().length; //입력받은 수의 자릿수 ex) 100 -> 3
var powLen = Math.pow(10, txtLen-1); //나눗셈 숫자 ex) 100/100, 200/100, 1000/1000
var txtDiv = txt/powLen; //나눗셈 결과
var txtResult = 0;
if(txtDiv < 2){
var pow = Math.pow(10, txtLen-2);
(pow == 1)? pow = 10 : pow; // 뺄셈 할 수의 기본값은 10
txtResult = txt - pow;
}else{
txtResult = txt - Math.pow(10, txtLen-1);
}
var tmpArray = txtResult.toString().split("");
//console.info("tmpArray - > " + tmpArray);
//5.1의 자리를 제외한 수를 반전해서 결과값에 span
var tmpCnt = tmpArray.length-2;
(tmpCnt < 0)? tmpCnt = 0 : tmpCnt; //array의 기본값을 0으로 설정 (-1 일 경우 처리)
for(var i = tmpCnt; i > -1; i--){
txtResult = txtResult + "" + tmpArray[i];
}
result.innerText = txtResult;
}
}
//enter키 이벤트
function key(e){
if(e.keyCode ==13){
goCalc();
document.getElementById("txtBox").focus();
}
}
</script>
</head>
<body>
<input type="textbox" id="txtBox" onkeypress="return key(event);"/> <input type="button" id="btnGo" value="go" onClick="goCalc();"/>
<h2 id="result"></h2>
<script>
document.getElementById("txtBox").focus();
</script>
</body>
</html>
clojure
(ns t1.core
(:require [clojure.math.combinatorics :as combo]))
;; ref: https://github.com/clojure/math.combinatorics
(defn p-skeleton
"
# >> (p-skeleton 5)
# ;=> ((1 0 0 0 1) (0 1 0 1 0) (0 0 1 0 0))
"
[n]
(for [x (range n 0 -2)]
(let [pad (take (/ (- n x) 2) (repeat 0))]
(if (= x 1)
(concat pad [1] pad)
(concat pad [1] (take (- x 2) (repeat 0)) [1] pad)))))
(defn skeleton->num
"
# (skeleton->num [0 1 0 1 0])
# ;=> 1010.0
"
[coll]
(loop [acc 0 n 0 [f & rst] coll]
(if-not f
acc
(recur (if (zero? f)
acc
(+ acc (* f (Math/pow 10 n))))
(inc n)
rst))))
(defn prepare-palindrome
"
# (prepare-palindrome [101 10 1])
# ;=> ((101 202 303 404 505 606 707 808 909) (0 10 20 30 40 50 60 70 80 90) (0 1 2 3 4 5 6 7 8 9))
"
[[f & rst]]
(if (== f 1)
(list (range 0 10 1))
(concat [(range f (* (dec f) 10) f)]
(map #(range 0 (* % 10) %) rst))))
(def sum (partial reduce +))
(defn palindrome-nums []
(->> (iterate inc 1)
(mapcat (fn [x]
(->> x
(p-skeleton)
(map skeleton->num)
(prepare-palindrome)
(apply combo/cartesian-product)
(map sum))))))
(defn nth-palindrome [nth]
(-> nth
(take (palindrome-nums))
(last)))
(time (map nth-palindrome [1 4 30 100 30000 1000000]))
;>> "Elapsed time: 0.022393 msecs"
;=> (0 3 202.0 909.0 2.00000002E8 9.0000000009E10)
public class EqualNumber {
public int findNumber(int seq){
int cnt=0;
int brkCnt=0;
while(true){
String tmp=String.valueOf(cnt);
String convertVal="";
for(int i=(tmp.length()-1);i>=0;--i){
convertVal=convertVal+tmp.charAt(i);
}
if(Integer.parseInt(convertVal)==cnt){
brkCnt++;
if(seq==brkCnt){
break;
}
}
cnt++;
}
return cnt;
}
/**
* @param args
* @throws Exception
*/
public static void main(String args[])throws Exception{
System.out.println(new EqualNumber().findNumber(100000));
}
}
파이썬 3.2.5 기준입니다.
def number_check(number):
number = str(number)
if number == number[::-1]: return True
else: return False
n = int(input("입력 : "))
number_list = []
number = -1
while len(number_list) != n:
number += 1
if number_check(number) == True:
number_list.append(number)
print(number)
Python 2.6.6에서 작성하였습니다.
10000 정도까지는 그냥 기다릴만한데, 그 이상되면 시간이 너무 많이 걸리네요.
#!/usr/bin/env python
def main():
number = input("Input number: ")
count = 0
i=0
while 1:
num = str(i)
if num == num[::-1]:
count +=1
if count == number:
print "Answer: "+num
break
i += 1
if __name__ == "__main__":
main()
숫자가 palindrome 인지를 체크하지 않고 순서대로 palindrome 을 만들어가는 방식으로 전환했더니 그럭저럭 만족할 만한 속도가 나오네요. 일단 만들고 sort등의 처리를 해야 해서 1,000,000 이상의 숫자는 Memory 오류가 발생합니다.
python 2.7
def palin(n):
result = [
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
"00","11", "22", "33", "44", "55", "66", "77", "88", "99"
]
fb = lambda aList:[str(b)+str(a)+str(b) for a in aList for b in range(0, 10)]
before = result
while True:
after = fb(before)
before = after
result.extend(after)
if len(result) >= n: break
#
# remove '0' startswith
#
result = filter(lambda a:not a.startswith("0"), result)
#
# make string to int
#
result = map(int, result)
#
# remove duplicate
#
result = list(set(result))
#
# sort
#
result.sort()
#
# finally, insert '0'
#
result.insert(0, 0)
return result[n-1]
print palin(1000000)
def num_order(count):
check = 0 # check the number matching with count
num = 0 # increase for checking
flag = False # finish flag
num = 0
while check < count:
str_num = str(num)
for i in range(0,int(len(str_num)/2+1)):
if str_num[i] == str_num[len(str_num)-1-i]:
flag = True
else :
flag = False
break
if i == int(len(str_num)/2)-i:
break
if flag == True:
check += 1
if check == count:
return num
print (num, check)
num += 1
return num
print ("ans:", num_order(3000))
속도는 엄청 느립니다..
package my;
public class AA {
public static void main(String[] args) {
System.out.println(check(100));
}
public static int check(long su){
int ct=0;
String a="";
String b="";
for (int num=0;ct!=su;num++){
a = String.valueOf(num);
b="";
for(int i=a.length()-1;i>=0;i--){
//10자리수 이상인데 첫번째 값이 0이면 카운트 넘어감
if (i==a.length()-1&&a.charAt(i)=='0'&&i>10) continue;
b=b+a.charAt(i);
}
//뒤집은 값이 같으면 실행
if(a.equals(b)){
System.out.println(a+"::"+b);
ct++;
}
}
return Integer.parseInt(a);
}
}
숫자로 연산하는게 확실히 문자열보다 빠르네요.
package my;
public class T {
public static void main(String[] args) {
System.out.println(check(10000));
}
public static long check(long su){
long num = -1;//0부터 증가할 숫자
int ct=0;//카운터
int max=1;
int min=1;
while(ct<su){
num++;//숫자 증가
int t=0; //자리수 변수
//자리수 구하기
for(long i=num;i>0;){
t++;
i=i/10;
}
max=1;//맥스값 자리수 구하기
for(int i=0;i<t;i++){
max=max*10;
}
max=max/10;
boolean f=true;
int tmax = max;
int tmin = min;
//해당 숫자 계산
for(int i=0;i<t;i=i+2){
int first=(int)num/tmax%10;
int last=(int)num/tmin%10;
//System.out.println("t: " +t+" num: "+num+" first:"+first+" last:"+last + "max: "+tmax+" min:"+tmin);
if(first!=last){
f=false;
break;
}
tmax=tmax/10;
tmin=tmin*10;
}
//같으면 카운터 증가
if(f){
//System.out.println(num+"같음");
ct++;
}else{
//System.out.println(num+"다름");
}
}
return num;
}
}
Perl
n 크기에 제한이 없으니 적어도 펄로는 숫자 하나씩 계산해서는 안됩니다. );
2k-1과 2k자리수의 회문이 각각 10k-1(10-1)개 이므로
개구간 (0,10n)내에서 0을 제외한 회문인 숫자는 n이 짝수일 때 2(10n/2-1), 홀수일 때 11(10(n-1)/2-2)개임을 알 수 있습니다. ∵ sum(9,9,90,90,900,900,9000,9000…)
뒷 부분은 귀찮아서 대충썼습니다. 200만 넣어도 잘 나옵니다.
use POSIX;
use strict;
sub getA{
my $i=shift;
if($i%2){
return 11*10**(($i-1)/2)-2
}else{
return 2*(10**($i/2)-1)
}
}
sub getXth{
my $x=shift;
$x--;
my @a=(0);
my ($i,$j,$k,$str);
push @a,getA(++$i) while($x>$a[$#a]);
return '0' if $x==0;
return '9'x$i if $x==$a[$#a];
$x-=$a[$#a-1];
if($i<2){
return $str=$x
}elsif($i<3){
return $str=$x.$x
}else{
$i-=2;
$str.=ceil($x/10**(ceil($i/2)));
$str.=sprintf("%0".ceil($i/2)."d",($x-1)%10**(ceil($i/2)));
$k=substr($str,0,length($str)-$i%2);
$str.=reverse($k);
}
return $str
}
루비입니다. IDLE님의 식을 참고했습니다.
class Palindrome
attr_reader :index
def initialize(index)
@index = index
end
def to_i
number.to_i
end
private
def size
unless @size
@size = 1
while max_index(@size) < index
@size += 1
end
end
@size
end
def number
unless @number
@number = half_number.to_s + half_number.to_s.reverse
@number[half_size] = "" if size.odd?
end
@number
end
def current_size_index
@current_size_index ||= index - max_index(size - 1)
end
def half_number
@half_number ||= current_size_index + ("9" * (half_size - 1)).to_i
end
def half_size
@half_size ||= (size.odd? ? (size + 1) : size) / 2
end
def max_index(n)
case n
when 0 then 0
when 1 then 10
when 2 then 19
else
9 * 10**((n + 1) / 2 - 1) + max_index(n - 1)
end
end
end
p Palindrome.new(1).to_i #=> 0
p Palindrome.new(4).to_i #=> 3
p Palindrome.new(11).to_i #=> 11
p Palindrome.new(30).to_i #=> 202
p Palindrome.new(100).to_i #=> 909
p Palindrome.new(30000).to_i #=> 200000002
p Palindrome.new(1000000).to_i #=> 90000000009
string, list method에 좀 많이 의존하는 성향이 있는거 같네요 제가 그래서 그런지 좀 느립니다. 회문을 만드는 방법에는 자연수와 자연수를 뒤집어서 이어붙이거나 자연수와 한자리 숫자 자연수를 뒤집은 것을 이어 붙이는 두가지 방법이 있음을 이용했습니다.
1 def str_reverse(string):
2 a = [x for x in string]
3 a.reverse()
4 return ''.join(a)
5
6 def generate(n):
7 ls_pal = [str(x) for x in range(10)]
8 ls_int = [str(y) for y in range(1, n+1)]
9 for half in ls_int:
10 ls_pal.append(half + str_reverse(half))
11 for digit in range(10):
12 digit = str(digit)
13 ls_pal.append(half + digit + str_reverse(half))
14 ls_pal = [int(z) for z in ls_pal]
15 ls_pal.sort()
16 return ls_pal
17
18 n = input()
19 print generate(n/2+1)[n-1]
vector 에 숫자 한개씩 때려넣고 begin, rbegin 으로 size/2 만큼 반복해서 비교합니다
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int nOrder = 0;
cin >> nOrder;
vector<int> vecTemp;
int nSeq = 0;
int nNow = 0;
while( 0 < nOrder )
{
nNow = nSeq++;
vecTemp.clear();
while( true )
{
vecTemp.push_back( nNow%10 );
nNow /= 10;
if( 0 == nNow )
break;
}
int nRepeatMax = vecTemp.size() / 2;
auto itFront = vecTemp.begin();
auto itBack = vecTemp.rbegin();
bool bDifferent = false;
for( int nRepeatNow=0; nRepeatNow<nRepeatMax; ++nRepeatNow )
{
if( (*itFront) != (*itBack) )
{
bDifferent = true;
break;
}
++itFront;
++itBack;
}
if( ! bDifferent )
{
--nOrder;
continue;
}
}
cout << nSeq-1 << endl;
return 0;
}
python 3.4 숫자를 문자열로 바꾸어 반으로 쪼개어 비교하는 방식으로 차리하였습니다.
def Fes(no):
count = 0;
number = 0;
while(1):
#한자리 숫자의 경우 그냥 출력, 두자리 이상부터 비교
if number in range(0,10):
print(number)
count += 1
else:
strNum = str(number)
a = ''
b = ''
#숫자를 문자열로 변환.
#짝수의 경우 문자열을 반으로 쪼개어 저장한다.
#홀수의 경우 가운데 문자를 빼고 반으로 쪼개어 저장한다.
if len(strNum)%2 == 0:
a = strNum[0:int((len(strNum)/2))]
b = strNum[int((len(strNum)/2)):]
else:
a = strNum[0:int((len(strNum)-1)/2)]
b = strNum[int((len(strNum)+1)/2):]
#뒤쪽 문자열을 역순으로 배치
temp = ''
for i in range(len(b)):
temp += b[-1*(i+1)]
#앞쪽 문자열과 비교하여 값이 같으면 화면에 출력하고 카운터 처리를 한다.
if a == temp:
print(number)
count += 1
if count == no:
break
number += 1
Fes(100)
import scala.annotation.tailrec
import scala.util.control.Breaks._
@tailrec
def getSomeValue(num: Int, count: Int): Int = {
if (count == 0) num - 1
else {
val numStr = num.toString
var i = 0
var flag = true
breakable {
for (i <- 0 to numStr.length / 2) {
if (numStr.charAt(i) != numStr.charAt(numStr.length - i - 1)) {
flag = false
break
}
}
}
if (flag) getSomeValue(num+1, count-1)
else getSomeValue(num+1, count)
}
}
getSomeValue(0,1)
getSomeValue(0,4)
getSomeValue(0,30)
getSomeValue(0,100)
getSomeValue(0,30000)
C 언어로 작성했는데 결과 값이 200000000 대 값 (2000000000 대 값에서 한계가 있습니다. 컴퓨터가 16 MB 라서요.) 이 나오려면 3분 이상 기다려야 하고 결과 값이 작을 수록 (회문수 순서 번호가 작을 수록) 빨리 나옵니다.
#include <stdio.h>
int main(void)
{
int arr1[50], arr3[50], arr5[50], arr6[50];
int a = 0, i = 0, j = 0, k = 0, p = 0, m = 1, s = 0, t = 0, u = 0, v = 10, x = 0, y = 0, z = 0;
printf("회문수를 호출하겠습니다. 몇번째 회문수를 호출할까요?\n");
scanf("%d", &a);
x = -1;
while(1)
{
x++;
s = x;
y = 0;
while(1)
{
i = 0;
j = 0;
t = s;
while(1)
{
k = s%10;
if(s==0)
break;
arr3[i] = k;
s = (int) s/10;
i++;
j++;
}
i = 0;
j = j-1;
for(i = 0; i <= j; i++)
{
arr5[i] = arr3[i];
arr6[i] = arr3[j-i];
}
i = 0;
for(i = 0; i <= j; i++)
{
if(arr5[i]==arr6[i])
{
if(i==j)
break;
}
else
break;
}
if(arr5[i]==arr6[i])
{
if(z==a)
break;
if(y==0)
{
z++;
}
break;
}
else if(arr5[i]!=arr6[i])
{
y++;
i = 0;
m = 1;
s = 0;
for(i = 0; i <= j; i++)
{
arr1[i] = (arr5[i]+arr6[i])*m;
m = m*10;
s = s+arr1[i];
}
if(t>=1050000000)
{
if(s<2100000000)
break;
}
if(s>2100000000 || s < 0)
break;
}
}
if(z==a)
break;
}
printf(" => %d\n", x);
return 0;
}
package rootcucu.codefight.old;
public class NumberPalindrome {
String number_palindrome(int n) {
int c=18,h;
for (n--;n>c;n-=c,c*=10);
h=c/18 + n -1;
n=n>c/2?h-=c/2:h/10;
String s = ""+ h;
for (;n>0;s+=n%10,n/=10);
return s;
}
public static void main(String[] args){
NumberPalindrome obj = new NumberPalindrome();
int[] numbers = new int[]{1, 4, 30, 100, 30000, 1000000};
for (int k:numbers){
System.out.println("k = " + k + ", k-th palindrome = " + obj.number_palindrome(k));
}
}
}
저도 이게 파이선문제인지 ㅋㅋ 수학문제인지 햇갈리지만 ㅋㅋ 수학문제로 풀었습니다 ㅋㅋ입력에서 1빼야지 답나오게되었어요..;;ㅋㅋ
#401.py
import math
#finding digits
def digits(n):
t=math.ceil(math.log10(n/2.0+1))
if math.log10(n+1)<=t:
return int(t),int(2*(10**(t-1)-1)),1
else:
return int(t),int(10**t-1),0
#finding answer
def ans(n):
result=[]
p=str(n-digits(n)[1]+(10**(digits(n)[0]-1)-1))
result=p+p[-1-digits(n)[2]::-1]
return result
Sub Main()
Dim n As Integer = Val(Console.ReadLine)
Dim iCnt As Long = 0,
cnt As Integer = 0
While cnt < n
Dim t As String = iCnt, d As Integer = 1
For i As Integer = 0 To Math.Ceiling(t.Length - 1 / 2) - 1
If t(i) <> t(t.Length - i - 1) Then
d = 0
Exit For
End If
Next
cnt += d
iCnt += 1
End While
Console.WriteLine(iCnt - 1)
Console.ReadLine()
End Sub
파이썬입니다. 길이가 짝수인 것과 홀수인것으로 나누어 구합니다.
n = 30000
l = [int(x) for x in [int(x + x[::-1]) for x in [str(x) for x in range(n)]] + [int(str(i) + str(x) + str(i)[::-1]) for i in range(n)[1:] for x in range(10)]] + range(10)[1:]
l.sort()
print l[n - 1]
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
int count = 0;
for(int i = 0;i <= int.MaxValue; i++)
{
string text =i.ToString();
if (i.ToString().Length == 1)
{
count++;
Console.WriteLine(text);
}
else if (i > 9 && i.ToString().Length % 2 == 0 && text.Substring(0, text.Length / 2) == text.Substring(text.Length/2,text.Length/2))
{
count++;
Console.WriteLine(text);
}
else if(i > 9&&i.ToString().Length%2 != 0 && text.Substring(0,text.Length/2)==text.Substring(text.Length/2+1,text.Length/2))
{
count++;
Console.WriteLine(text);
}
if(count == n)
{
Console.WriteLine("{0} -> {1}",n,i);
break;
}
}
}
Swift로 풀어보았습니다.
import Foundation
extension String {
var count: Int {
get {
return self.characters.count
}
}
var beforeHalf: String {
get {
return self.substringToIndex(self.startIndex.advancedBy(self.count / 2))
}
}
var afterHalf: String {
get {
return self.substringFromIndex(self.endIndex.advancedBy(-self.count / 2))
}
}
var reverse: String {
get {
return Array(self.characters).reverse().reduce("") { $0 + String($1) }
}
}
}
extension Array {
subscript (safe index: Int) -> Element? {
return indices ~= index ? self[index] : nil
}
}
func checkIndex(n: Int) -> Int {
var list: [Int] = []
(0..<10).forEach { list += [$0] }
var i = 10
while list[safe: n] == nil {
let str = String(i)
if str.beforeHalf == str.afterHalf.reverse {
list += [i]
}
i++
}
return list[safe: n] ?? 0
}
checkIndex(1)
checkIndex(4)
checkIndex(30)
checkIndex(100)
checkIndex(30000)
checkIndex(1000000)
python3입니다. 중간에 적절히 걸러내는 부분을 추가하면 많이 빨라질텐데, 일단은 naive한 코드입니다.
n = int(input())
i = cnt = 0
while(1):
s = str(str(i)[::-1])
if (str(i) == s):
cnt = cnt + 1
if cnt == n:
print (i)
break
i = i + 1
cnt=0
def insert_mid(strn,m,n):
return strn[:len(strn)/2]+m*n+strn[len(strn)/2:]
def recursive(i,strn,n):
global cnt
if i<=2:
for x in range(10):
cnt+=1
if cnt==n:
strn=insert_mid(strn,str(x),i)
return (1,strn)
return (0,strn)
else:
for x in range(10):
ret=recursive(i-2,insert_mid(strn,str(x),2),n)
if ret[0]: return ret
return ret
def palindrome(n):
i=1
total=10
m=n
while total<n:
m=n-total
total+= 9*(10**(i/2))
i+=1
if i<=1:
ret=recursive(i,'',m)
if ret[0]:
return ret[1]
for x in range(1,10):
ret=recursive(i-2,str(x)*2,m)
if ret[0]:
return ret[1]
print palindrome(1)
속도는 꽤 빠른데 코드가 좀 드럽네요. 전역변수가 넘 찝찝.. 좀더 수정해봐야겠습니다. 값을 print만 하는거면 return을 튜플이아닌 정수값으로줘서 속도가 훨 빨라질수있습니다
def num_palindrome(i,isComp):
if isComp:
return 10 if i==1 else 9*(10**((i-1)/2))
return 10*(10**((i-1)/2))
def palindrome(i,k,isOutside):
if i<=2:return str(k-1)*i
total=0
next=k
for j in range(0+(1 if isOutside else 0),10):
next=k-total
total+=num_palindrome(i-2,False)
if k<=total:return str(j)+palindrome(i-2,next,False)+str(j)
def nth(n):
i=1
total=10
k=n
while total<n:
i+=1
k=n-total
total+= num_palindrome(i,True)
return palindrome(i,k,True)
print nth(1000000)
파이썬2.x입니다. 드뎌 만족할만한 코드가 나온듯요 속도도 빠르고 이정도면 군더더기 없는듯? 부족한점 지적부탁드립니다
if __name__ == '__main__':
n = input('Enter n: ')
count = 0
if int(n) < 11:
nth_num = int(n)-1
else:
nth_num= 10
count = 10
while count != int(n):
x = list(str(nth_num))
quo, rem = divmod(len(x),2)
x1 = x[0:quo]
x2 = x[quo+rem:]
x2.reverse()
if ''.join(x1) == ''.join(x2):
count += 1
nth_num += 1
nth_num -= 1
print(nth_num)
python 3.4
palind = int(input("Enter a number :"))
count =0
x=0
while palind-count:
if (str(x)[::-1] == str(x)):
count += 1
x += 1
print(x-1)
'''
파이썬 2.7 입니다.
숫자를 일일이 체크하는 방법이 아니고,
입력값 n으로 부터 출력값을 바로 계산하는 알고리즘입니다.
숫자가 앞뒤로 거울상이라는 점을 이용해서
앞쪽 거울상을 먼저 계산하고
앞뒤로 거울상을 이어붙여서 출력합니다.
출력되는 숫자의 자리수가 1일때 원본 거울상의 갯수는 9개(0제외하고 1~9)
2일때 9개(1~9)
3일때 90개(10~99) -> 101, 111, 121, 131, .... 중 앞 2자리 숫자
4일때 90개(10~99) -> 1001, 1111, 1221, 1331, ... 중 앞 2자리 숫자
5일때 900개(100~999) -> 10001, 10101, 10201, ... 중 앞 3자리 숫자
....
이런식으로 누적시켜서 출력되는 숫자의 한쪽 거울상의 자릿수를 구하고,
그 전까지의 누적갯수를 n에서 빼주고 10의 (자릿수-1)/2제곱을 더해주면 한쪽 거울상을 구할 수 있습니다(변수 image)
'''
def palin(n):
if n == 1 : return 0
total = 1 #0때문에 0이 아닌 1로 해줌
d = 1 #정답의 자리수
while True:
total += 9*10**((d-1)/2)
if total >= n :
total -= 9*10**((d-1)/2)
break
d+=1
image = str(n-total+10**((d-1)/2) - 1) # -1을 해준 것은 수열의 첫번째가 0이기 때문.
if d&1 == 1: #정답의 자릿수가 홀수냐 짝수냐에 따라서 거울상을 구하는 방법이 다름
return image[:-1]+reduce(lambda x,y:y+x, image)
else :
return image+reduce(lambda x,y:y+x, image)
while True:
n = int(raw_input())
if n == - 1 : break
print palin(n)
print
'''
출력예시
22
121
30
202
100
909
30000
200000002
1000000
90000000009
1000000000000000000
90000000000000000000000000000000009
100000000000000000000000000000000000000000
900000000000000000000000000000000000000000000000000000000000000000000000000000009
'''
print "This is the program that gets you the nth palindrome number\n"
n = input("input n:\n")
def is_palindrome(x):
if len(str(x)) == 1:
return True
elif len(str(x)) != 1 and len(str(x))%2 != 0 :
for i in range((len(str(x))-1)/2):
if str(x)[i] != str(x)[len(str(x))-1-i]:
return False
break
else:
return True
else:
for i in range(len(str(x))/2):
if str(x)[i] != str(x)[len(str(x))-1-i]:
return False
break
else:
return True
print is_palindrome(1234321)
cntr = 0
m = 0
while cntr<n:
if is_palindrome(m) == True:
cntr+=1
m+=1
else:
m+=1
else:
print "the %dth palindrome number is %d" %(n, m-1)
리스트를 만들까 했는데, N 이 무제한이므로 그냥 하나하나 세었습니다.
Ruby
두 가지로 풀이(one-liner,빠른풀이). 10**10000번째 즈음부터 급격히 느려집니다, 자릿수 계산을 행렬로 바꾸면 나아지겠네요.
(0..1.0/0.0).lazy.select{|n|n==n.to_s.reverse.to_i}.take(nth).force.last
빠른 풀이
자릿수별 거울수 갯수는 수식(9x10xx(d/2-(d%2^1))으로 일반화된다. 이를 이용해서 거울수의 자릿수와 위치를 계산할 수 있고, 거울수의 앞머리를 만들어낼 수 있다. 만들어진 앞머리를 뒤집어 붙이면 구하고자 하는 거울수가 만들어진다.
idx = ->n { (2..n).reduce([10]) {|a,d| a[-1]<n ? [d, n-a[-1]-1, a[-1]+9*10**(d/2-(d%2^1))] : (break a)} }
gen = proc {|d,pos| h = 10**(d/2-(d%2^1))+pos; [h, (h/10**(d%2)).digits]*'' }
pal = ->n { n>10 ? gen[*idx[n]].to_i : n-1 }
Test
nths, pals = [1,4,30,100,30000,1000000], [0,3,202,909,200000002,90000000009]
expect( nths.map(&pal) ).to eq pals
expect( Benchmark.realtime { pal[10**1000]} ).to be_between(0.001, 0.02)
# performance
nth = [10**10, 10**100, 10**1000, 10**10000, 10**100000]
Benchmark.bmbm {|x| nth.each {|n| x.report("%e" %n) {pal[n]} } }
Rehearsal -------------------------------------------------
1.000000e+10 0.000000 0.000000 0.000000 ( 0.000027)
1.000000e+100 0.000000 0.000000 0.000000 ( 0.001706)
Inf 0.020000 0.010000 0.030000 ( 0.016068)
Inf 0.850000 0.040000 0.890000 ( 0.893889)
Inf 229.680000 4.940000 234.620000 (235.791773)
-------------------------------------- total: 235.540000sec
user system total real
1.000000e+10 0.000000 0.000000 0.000000 ( 0.000038)
1.000000e+100 0.000000 0.000000 0.000000 ( 0.000471)
Inf 0.000000 0.000000 0.000000 ( 0.008673)
Inf 0.830000 0.030000 0.860000 ( 0.857369)
Inf 236.550000 5.540000 242.090000 (246.520645)
Output
pal[10**5000] #=> 길이가 10000인 palindrome '9000.....009'가 출력됨.
Python3로 generator를 활용하여 작성하였습니다.
이 문제는 연산속도를 어떻게 단축시키느냐가 포인트네요~ 파이썬으로 돌려보니 당췌 언제 답이 나올런지..
이 숫자에는 법칙이 있네요~ 123을 입력하면 2332 234를 입력하면 13431 나중에 이렇게 구현해서 올려봐야 겠당
def genPalindrome():
n = 0
while True:
digit = str(n)
if digit == digit[::-1]:
yield n
n += 1
n = int(input("input : "))
lastPalindrome = 0
palindrome = genPalindrome()
for i in range(n):
lastPalindrome = next(palindrome)
print(lastPalindrome)
결과
Input : 1
0
Input : 4
3
Input : 30
202
Input : 100
909
input : 3000
2000002
두 가지 코드입니다. 위는 하나하나 체크하는 방식, 아래는 거울수를 생성하여 찾는 방식 입니다. 아래 것이 압도적으로 빠릅니다. 파이썬 3.5.1
from itertools import *
while __name__ == '__main__':
objectNumber = int(input('입력: '))
counter = count()
li = []
while 1:
num = counter.__next__()
notMirror = False
for i in range(len(str(num))//2):
if str(num)[i] != str(num)[-1-i]:
notMirror = True
break
if not notMirror:li.append(num)
if len(li) == objectNumber:break
print(li[-1])
while __name__ == '__main__':
objectNumber = int(input('입력: '))
nlist = []
plist = []
i = 0
while 1:
nlist.append([])
for j in range(0, 10):
if i == 0 :nlist[i].append(str(j))
elif i == 1:nlist[i].append(str(j)*(i+1))
else:
for k in list(str(j)+x+str(j) for x in nlist[i-2]):nlist[i].append(k)
for y in nlist[i]:
if y == '0' or (y[0] != '0' and y != '0'):plist.append(int(y))
if len(plist)>objectNumber:break
i += 1
print(sorted(list(set(plist)))[objectNumber-1])
0~99 까지의 대칭수는 자리 수 별로 1자리: 10개 2자리: 9개
이렇게 됩니다.
n 자리 대칭수가 몇 개 있는지 생각해보면 우선 9자리를 볼 때 abcdexxxx 자리수를 반으로 나눈 자리의 수의 개수만큼 있을 수 있습니다. 10자리의 경우는 abcdexxxxx 가 될테구요. abcde -> 10000 ~ 99999 까지 가 있습니다.
이렇게 자리수 마다 몇 개의 대칭수가 있는지 계산해서 차곡차곡 더해 n 번째보다 한자리 작은 수의 개수를 n 에서 빼고 abcdefg 가 남았다면, 이를 뒤집어서 대칭으로 만들어주면 됩니다. 단 자리수에 따라서 어디까지 잘라 뒤집어 붙일지를 결정해야 하지요.
livescript 인데 뭔가 정리가 안되는듯;;;
np = (l) ->
| l < 2 => 10
| l < 3 => 9
| _ =>
m = Math.ceil l / 2
10 ^ m - 10 ^ (m - 1)
main = (n) ->
if n < 10 => return "#{n - 1}"
if n < 20 => return "#{n % 10 * 11}"
p = 0
i = 1
while n > np i
n -= np i
i += 1
v = "#{10^(Math.floor i / 2 ) + n - 1}".split ''
if i % 2 == 1 then v.slice! ++ v.reverse!.slice 1 else v.slice! ++ v.reverse!
|> (.join '')
[1 4 30 100 30000 1000000].map main
|> console.log
cnt = 0
i = -1
while(cnt!=n) :
i+=1
str = "%d" %i
if(len(str)==1) :
pass
else :
for j in range(0, int(len(str)/2)) :
if(str[j] == str[-(j+1)]) :
pass
else :
cnt-=1
break
cnt+=1
print(i)
try:
while True:
c = int(input())
n = 0
while True:
if str(n) == str(n)[::-1]:
c -= 1
if c == 0:
print(n)
break
n += 1
except KeyboardInterrupt:
pass
t=0
k=0
def indexcal(a): #규칙성을 따라 계산하는 방법.
b=str(a)
c=""
if b[0]=="1" and b[1]=="0" and b!="10": # 10으로 시작하는 경우 앞자리르 9로 보정
c=str(int(b[0:2])-1)+b[2:len(b)-1]
d="".join(reversed(c))
return c+b[-1]+d
elif b[0]=="1" and b[1]!="0": #1로 시작하는 경우
c=b[1:]
d="".join(reversed(c))
return c+d
elif b=="10": #10 일때 909를 출력하는 것을 보정
return 9
else:
c=str(int(b[0])-1)+b[1:len(b)-1]
d="".join(reversed(b[1:len(b)-1]))
return c+b[-1]+d+str(int(b[0])-1)
while 1:
n = int(input())
if n==0:break
while t!=n:
nums=str(k)
if nums=="".join(reversed(nums)):
t=t+1
k=k+1
print("string calculation",nums)
t=0
k=0
print("indexing canculation",indexcal(n))
속도가 느린 방법이래서 다른 방법으로 계산해서 만들어 보았습니다.
package main
import (
"strconv"
"fmt"
)
func Reversable(v int) bool {
s := strconv.Itoa(v)
for i := 0; i < len(s)/2; i++ {
if s[i] != s[len(s)-i-1] {
return false
}
}
return true
}
func main() {
var n int
fmt.Scan(&n)
c := 0
i := 0
for {
if Reversable(i) {
c++
if c == n {
break
}
}
i++
}
fmt.Println(i)
}
Delphi 2010
procedure TForm4.fnSeachSameValue(C_Targer: Integer);
var
i, f: integer;
j, n, n2, nBit, nCnt: integer;
bOk: boolean;
StartValue: DWORD;
C_Digit: array [0 .. 100] of byte;
s: string;
begin
// 압뒤가 같은 수 찾기
nCnt := 0;
FillChar(C_Digit, sizeof(C_Digit), #0);
n := -1;
nBit := 1;
StartValue := GetTickCount;
for f := 0 to maxInt do
begin
for i := 0 to 999999 do
begin
Inc(n);
if n = 10 then
begin
n := 0;
for j := 1 to 100 do //100자릿수 까지
begin
if C_Digit[j] = 9 then
begin
if nBit = j then
Inc(nBit);
C_Digit[j] := 0;
end
else
begin
Inc(C_Digit[j]);
break;
end;
end;
end
else
C_Digit[1] := n;
n2 := (nBit) div 2;
bOk := true;
for j := 1 to n2 do
if C_Digit[j] <> C_Digit[nBit - j + 1] then
begin
bOk := False;
break;
end;
if bOk then
begin
Inc(nCnt);
if nCnt >= C_Targer then
begin
StartValue := GetTickCount - StartValue;
s := '';
for j := 1 to nBit do
s := IntToStr(C_Digit[j]) + s;
Memo1.Lines.Add(format('Target Count: %d, value: %s, %.2n sec',
[C_Targer, s, StartValue / 1000]));
break;
end;
end;
end;
if nCnt >= C_Targer then
break;
end;
end;
procedure TForm4.Button3Click(Sender: TObject);
begin
fnSeachSameValue(0);
fnSeachSameValue(4);
fnSeachSameValue(30);
fnSeachSameValue(100);
fnSeachSameValue(30000);
fnSeachSameValue(100000);
end;
음 입력이 1000 넘어가면서 점점 느려지네여.... 혹시 빨리 처리되는 알고리즘이나
맨마지막 예제와 같이 double형도 초과하는 변수를 처리해야하는 방법알고 계신분 있나요 ㅠㅠ??
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int getSize(int val);
bool verdict(int* val, int size);
void main(void) {
int input;
scanf("%d", &input);
double n = 10;
int* val;
int count = 1;
int size;
for(double i = 1; i < n ; i++) {
size = getSize(i);
int k = 0;
int temp = i;
val = (int*) malloc (sizeof(int) * size);
for(double j = size-1; j >= 0 ; j--) {
val[k] = temp/pow(10.0, j);
temp = temp%(int) pow(10.0, j);
k++;
}
if(true == verdict(val, size)) {
count++;
if(count == input) {
for(int j = 0 ;j < size ; j++)
printf("%d", val[j]);
exit(0);
}
}
n++;
free(val);
}
}
int getSize(int val) {
int k = 1;
int size = 0;
for(int i = 0; i<val ; i++) {
if(val/k !=0) {
k = k*10;
size++;
}
}
return size;
}
bool verdict(int* val, int size) {
int count = 0;
if(size == 1)
return true;
for(int i = 0; i < (size/2); i++) {
if(val[i] == val[(size-1)-i])
count++;
}
if(count == size/2)
return true;
else
return false;
}
public long Palindrome(int order)
{
long temp = 0;
int Palcnt = 0;
char[] iChar = { ' ' };
string iReversed = "";
for(long i = 0; ; i++)
{
iChar = i.ToString().ToCharArray();
Array.Reverse(iChar);
iReversed = new string(iChar);
if(iReversed == i.ToString())
{
temp = i;
Palcnt++;
}
if(Palcnt == order)
{
break;
}
}
return temp;
}
풀긴 풀었는데 민망할정도로 오래 걸립니다;; 공부 더해야 할듯하네요;
이제 100~999 라는 세자리 숫자로 앞뒤같은 수를 만들어보면.. 가운데겹침이 되는 900개와 겹침없는 900개로 1800개가 만들어지는 걸 알수 있습니다.
원하는 순서의 값을 찾으려면 먼저 몇자리 숫자인지를 위의 규칙으로 찾아내고, 그 다음은 앞뒤같은수를 만들어서 해당 위치의 숫자를 찾을 수 있을 것 같습니다.
pal :: Int -> Int
pal 0 = 1
pal n = go (n-2) 9 1
where go n count digits = if n < count then mkPal1 (range digits !! n)
else if n < count*2 then mkPal2 (range digits !! (n-count))
else go (n-count*2) (count*10) (digits+1)
range digits = [10^(digits-1) .. 10^digits-1]
mkPal1 n = let s = show n in read (s ++ tail(reverse s))
mkPal2 n = let s = show n in read (s ++ reverse s)
#python 2.7.xx
insert = 100
x,cnt = 0,0
while insert != cnt:
if str(x) == str(x)[::-1]:
cnt += 1
print cnt, x
x +=1
num, count, a = int(input()), 0, '-1'
while num != count:
a = str(int(a) + 1)
b = a[::-1]
if a == b:
count += 1
print(int(a))
#### 2017.01.27 D-391 ####
package sss;
/*0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, ... 과 같이
* 0 이상의 앞뒤가 같은 수를 크기 순으로 나열할 때, n 번째 수를 계산하는 프로그램을 작성하라.
n은 1부터 시작하며 크기에는 제한이 없다.
1부터 시작해서 Panlindrome을 저장해서 n을 찾는 것은 시간이 너무 오래 걸릴거 같습니다.(ex. n = 1000000)...
그래서 규칙을 찾아봤는데
1의자리 : 9개 + 1개(n=0)
10의자리 : 9개
100의자리 : 9*10
1000 : 9*10
10000 : 9*(10*10)
100000 : 9*(10*10)
1000000: 9*(10*10*10)
이런 규칙을 띄고 있습니다.
1. 몇자리 수인지 확인한다.
- 1의 자리라면 10의 0제곱이니 0이 되어야겠지만 밑에서
palindrome을 구하기위해서 배열을 쓸 예정이라서 1로 설정했습니다.
나중에 배열을 만들 때 size를 지정해 줄려고...
2. 가장 바깥쪽의 숫자를 확인한다.
3. 그 다음 바깥쪽으로 부터해서 안 쪽을 채워 넣는다.
- for문 처음에 나누기 9를 한 이유는 맨 처음 자리수는 1~9 -> 9개 밖에 없기 때문입니다.
temp : (바깥 쪽의 숫자가 1씩 바뀔 때마다 생기는 가짓수)
check + temp > n을 반복합니다.
4. 맨 앞자리와 뒷자리는 1부터 시작해야되는데 0부터 시작했으므로 1을 추가했습니다.
*/
public class Panlindrome_int {
public static void main(String[] args) {
int i;
int n = 30; //입력
int check = 1;
if(n==1)
System.out.println("0");
else{
int temp = 9;
int digit = 1;//자릿수
//1
while(true){
if(check+temp>=n)break;check+=temp;digit++;
if(check+temp>=n)break;check+=temp;digit++;
temp*=10;
}
int[] palin = new int[digit];
//2 + 3
for(temp /= 9,i = 0;check < n;temp/=10, i++){
for(int j = 0; j < 10; j++){
if(check+temp>n)break;
else if(check+temp==n)check+=temp;
else{
check+=temp;
if(i == (digit-1)-i)palin[i]++;
else{palin[(digit-1)-i]++;palin[i]++;}
}
}
}
//4
if(digit == 1) palin[0]+=1;
else {palin[(digit-1)]++;palin[0]++;}
for(int k : palin)
System.out.print(k);
}
}
}
import java.math.BigDecimal;
import java.util.Scanner;
public class SameNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigDecimal n = sc.nextBigDecimal();
BigDecimal t = n;
BigDecimal r = BigDecimal.ZERO;
while (true) {
t = t.divide(BigDecimal.TEN);
if (t.compareTo(BigDecimal.ONE) == -1) {
break;
}
r = r.add(BigDecimal.ONE);
}
BigDecimal a = pow(r);
BigDecimal c = n.subtract(a);
if (c.compareTo(a) == -1 && r.compareTo(BigDecimal.ONE) == 1) {
c = n.subtract(a.divide(BigDecimal.TEN));
}
String d = String.valueOf(c);
StringBuffer e = new StringBuffer(d.substring(0, d.length() - (c.compareTo(BigDecimal.valueOf(2)) == 1 ? 1 : 0)));
System.out.println(d + "" + e.reverse());
}
private static BigDecimal pow(BigDecimal r) {
BigDecimal c = BigDecimal.ZERO;
BigDecimal d = BigDecimal.ONE;
while (c.compareTo(r) == -1) {
d = d.multiply(BigDecimal.TEN);
c = c.add(BigDecimal.ONE);
}
return d;
}
}
package dojang15;
import java.util.*;
public class Symmetry {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int input = console.nextInt();
int count = 0;
int value = 0;
while (true) {
String temp = Integer.toString(value);
if (isSymmetry(temp, 0, temp.length() - 1)) {
count++;
}
if(count == input)
break;
else
value++;
}
System.out.println(value);
console.close();
}
public static boolean isSymmetry(String target, int l, int r) {
if (l >= r)
return true;
else
return target.charAt(l) == target.charAt(r) && isSymmetry(target, l + 1, r - 1);
}
}
그냥 단순하게 짰는데 겁나 느리네요...ㅠ
def mirrnum(n):
i=0
j=1
hub_n = n
if n <= 9:
return n
elif n <= 18:
return int(str(n-9)*2)
else:
while hub_n - 9*(10**i) > 0:
if j==1:
hub_n = hub_n - 9*(10**i)
j=2
else:
hub_n = hub_n - 9*(10**i)
i+=1
j=1
if j==1:
hub_result = str(hub_n + int('0'+'9'*i))
hub_len = len(hub_result)
result = hub_result
for l in range(hub_len-1):
result += hub_result[hub_len-2-l]
return int(result)
else:
hub_result = str(hub_n + int('0'+'9'*i))
hub_len = len(hub_result)
result = hub_result
for l in range(hub_len):
result += hub_result[hub_len-1-l]
return int(result)
#include<stdio.h>
int Num(int i);
int range = 1000000000;
int main()
{
int input;
int num;
int count = 0; // input 번째의 카운트
int i, j;
int answer;
int temp = 1,
I,
L = 0;
scanf("%d", &input);
for (i = 0; ; i++)
{
num = Num(i);
temp = 1;
L = 0;
I = i;
for (j = 0; j < num; j++)
{
L += I / range * temp;
temp = temp * 10;
}
if (I == L)
{
count++;
}
if (count == input)
{
answer = i;
break;
}
}
printf("%d", answer);
}
int Num(int i)
{
range = 1000000000;
int counnt = 10;
while (1)
{
if (i == 0)
{
range = 1;
counnt = 1;
break;
}
else if (i / range == 0)
{
}
else
{
break;
}
range = range / 10;
counnt--;
}
return counnt;
}
def reverse_same(number):
b=str(number)
b=list(b)
b.reverse()
c="".join(b)
c=int(c)
if number == c :
return True
else :
return False
def tot(rel):
cnt=0#count reverse same number
i=0#자연수의 흐름
if rel<10:
return rel-1
else:
while cnt<rel:
if reverse_same(i):
cnt+=1
i+=1
else:
i+=1
return i-1
print(tot(30000))
먼저 각 자리수에 대한 팔린드롬의 수를 알아내는 function 을 만들었습니다.
입력값을 넘지 않는 최대수를 sum 하고난 후
sum 이 입력값과 같다면
해당 자리수의 마지막 수(0, 9, 99, 999, ...)이므로 계산해서 리턴
sum 이 입력값보다 작다면
그 다음 자리수의 반을 잘라(물론 홀수면 [n/2]+1이겠죠) 10 부터 남은 개수만큼 계산하고서
자리수가 짝수면 뒤집어 붙여주고
자리수가 홀수면 마지막자리수를 없애고 뒤집어 붙입니다.
속도는 빠르네요. 입력값이 아닌 자리수에 대해 O(n) 이에요.
cache 를 사용하면 더 빨라질 것 같은데 그냥 pass
javascript(ES6)
var countByDigit = n => Math.ceil(9 * Math.pow(10, Math.ceil(n / 2) - 1));
var palindrome = function(n) {
let i, sum = 0;
for (i = 0; sum <= n; i++) {
sum += countByDigit(i);
}
sum -= countByDigit(i - 1);
var remain = n - sum;
if (remain === 0) {
var pal = Math.pow(10, i - 2) -1;
return pal;
}
var digit = Math.ceil(i / 2);
var start = Math.pow(10, digit - 1);
var end = start + remain - 1;
var offset = (i - 1) % 2;
var reverse = ("" + end).split("").reverse().slice(offset).join("");
var pal = "" + end + reverse;
return pal;
};
console.log(palindrome(1));
console.log(palindrome(4));
console.log(palindrome(30));
console.log(palindrome(100));
console.log(palindrome(30000));
console.log(palindrome(1000000));
전형적인 군수열 문제입니다. 전체적으로 몇 번째 숫자를 구하려 해도 평균 770,000 nano second 정도 걸리는 로직입니다.
첫 번째 군은 0~9의 한자리 숫자입니다.(1~10)
두 번째 군은 11~99의 두자리 숫자입니다.(11~19)
세 번째 군은 101~999의 세자리 숫자입니다. 이전 군의 바로 다음 순번부터 9 * 10^1 만큼의 순번까지 항이 존재합니다.
네 번째 군은 1001~9999의 네자리 숫자입니다. 이전 군의 바로 다음 순번부터 9 * 10^1 만큼의 순번까지 항이 존재합니다.
다섯 번째 군은 10001~99999의 다섯자리 숫자입니다. 이전 군의 바로 다음 순번부터 9 * 10^2 만큼의 순번까지 항이 존재합니다.
여섯 번째 군은 100001~999999의 여섯자리 숫자입니다. 이전 군의 바로 다음 순번부터 9 * 10^2 만큼의 순번까지 항이 존재합니다.
.
.
.
2n+1 번째(n>=1) 군은 2n+1자리 숫자입니다. 이전 군의 바로 다음 순번부터 9 + 10^n 만큼의 순번까지 항이 존재합니다.
2n+2 번째(n>=1) 군은 2n+2자리 숫자입니다. 이전 군의 바로 다음 순번부터 9 + 10^n 만큼의 순번까지 항이 존재합니다.
2n+1번째 이상의 각 군에 속하는 항들은 1~n 번째까지의 대칭형 자릿수와 n+1번째 중앙자릿수를 갖습니다.
2n+2번째 이상의 각 군에 속하는 항들은 1~n+1 번째까지의 대칭형 자릿수를 갖습니다.
1번째 자릿수는 1~9까지
나머지 자릿수는 0~9까지를 갖습니다.
1번째 자릿수는 10^n의 몫으로 결정되며
2~n번째 자릿수는 앞선 자릿수의 나머지를 10^(n-1) ~ 10^1 로 나눈 몫으로 결정됩니다.
n+1번째 자릿수는 n번째 자릿수를 10^1 로 나눈 나머지로 결정됩니다.
import java.util.Scanner;
public class Symmetric{
/* 입력된 자연수가 1~19인지 그 이후인지 판별하여 맞는 값을 리턴합니다. */
public static long judgeNumber(long number){
if(number < 1){
System.out.println("잘못된 입력입니다.");
return -1;
}
/* 첫 번째 군 */
else if(number < 11) return number - 1;
/* 두 번째 군 */
else if(number < 20) return (number - 10) * 11;
/* 세 번째 이상 군 */
else return judgeNumber2(number);
}
/* 몇 번째 군에 속하는지 확인하고 숫자를 만들기 위한 주요 변수의 값을 정하는 메소드 */
private static long judgeNumber2(long number){
/* n번째 숫자가 어느 자릿수 군에 속하는지 확인하기 위한 변수 */
long serial = number - 19;
/* 계산 결과가 담길 변수 */
long calc = serial;
/* 제곱 계산을 위한 변수 */
int power = 1;
/* 제곱 결과가 실릴 변수 */
long pow = 0;
/* n` = n-19 */
/* 3번째 군 : (n`>=1) n` = 1~90(90) */
/* 4번째 군 : (n`>=1) n` = 91~180(90) */
/* 5번째 군 : (n`>=1) n` = 181~1080(900) */
/* 6번째 군 : (n`>=1) n` = 1081~1980(900) */
/* 7번째 군 : (n`>=1) n` = 1981~10980(9000) */
/* 8번째 군 : (n`>=1) n` = 10981~19980(9000) */
/* 범위가 9 * 10^m 만큼 커져가며 합산됩니다. */
System.out.println(number + "번째 대칭수가 어느 군에 속하는지 확인합니다.");
while(calc > 0){
pow = (long) (Math.pow(10, power++)) * 18;
calc = calc - pow;
}
calc = calc + pow;
power = power - 1;
pow = (long) (Math.pow(10, power)) * 9;
int series = 0;
/* 홀수개의 자릿수를 갖는지 짝수개의 자릿수를 갖는지 확인합니다. */
if(calc - pow > 0){
series = (power * 2) + 2;
calc = calc - pow;
}else{
series = (power * 2) + 1;
}
/* calc에 해당 군 내에서 몇 번째 숫자인지가 기록됩니다. */
System.out.println(number + "번째 대칭수는 " + series + "자리 수인 " + series + "번째 군의 " + calc + "번째 숫자입니다.");
return makeNumber(series, calc);
}
/* 리턴할 숫자를 만드는 메소드 */
public static long makeNumber(int series, long calc){
int power = 0;
/* 대칭형이기 때문에 실질적으로 결정해야할 자릿수는 절반이거나 절반을 반올림 해야 합니다. */
/* 예를 들어 7자리 수는 ABCDCBA 이므로 4개의 자릿수가 필요합니다. */
/* 예를 들어 10자리 수는 ABCDEEDCBA 이므로 5개의 자릿수가 필요합니다. */
if(series%2 == 1){
power = (series + 1) / 2;
}else{
power = series / 2;
}
/* 몫과 나머지를 이용해 자릿수를 만들어 담을 배열입니다. */
long[] Numbers = new long[power];
long quotient = calc;
long remain = 0;
/* 가장 큰 자릿수는 가장 바깥 숫자를, 더 작은 자릿수일 수록 안쪽의 숫자를 결정합니다. */
for(int i=1;i<power;i++){
quotient = calc / (long) (Math.pow(10, power-i));
remain = calc % (long) (Math.pow(10, power-i));
/* 예를 들어 5, 6번째 군의 숫자들은 ABCBA, ABCCBA 형태입니다. */
/* i==1일 때 100으로 나눈 몫으로 A를 결정합니다. */
/* calc(순번)가 1~100번째 숫자라면 A=1이 됩니다. */
/* calc(순번)가 101~200번째 숫자라면 A=2가 됩니다. */
/* B는 i==2일 때 결정됩니다. 앞서 나눈 나머지를 다시 10으로 나눈 몫으로 B를 결정합니다. */
/* 나머지가 1~10번째 숫자라면 B=0이 됩니다. */
/* 나머지가 11~20번째 숫자라면 B=1이 됩니다. */
if(i==1){
if(remain != 0) quotient += 1;
}else{
if(remain == 0) quotient -= 1;
}
Numbers[i-1] = quotient;
calc = remain;
}
if(remain == 0) remain = 9;
else remain -= 1;
Numbers[power - 1] = remain;
/* 홀수개의 자릿수를 갖는지 짝수개의 자릿수를 갖는지에 따라 나누어 숫자를 붙여 완성합니다. */
String sReturnNumber = "";
if(series%2 == 1){
for(int j=0;j<power;j++){
sReturnNumber += Numbers[j];
}
for(int k=power-2;k>=0;--k){
sReturnNumber += Numbers[k];
}
}else{
power = series / 2;
for(int j=0;j<power;j++){
sReturnNumber += Numbers[j];
}
for(int k=power-1;k>=0;--k){
sReturnNumber += Numbers[k];
}
}
long returnNumber = Long.parseLong(sReturnNumber);
return returnNumber;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("자연수를 입력해주세요.");
long number = scan.nextLong();
long start = System.nanoTime();
long result = judgeNumber(number);
if(result == -1) System.exit(0);
System.out.println("대칭형 음이 아닌 " + number+ "번째 정수는 '" + result + "'입니다.");
long end = System.nanoTime();
long time = end - start;
System.out.println(time);
}
}
#include<stdio.h>
#define MAX 100
#define FALSE 0
#define TRUE 1
int Is_Palindrome(int num);
int main(void)
{
int N; //원하는 수
int i; //반복문 변수
int count = 0; //Palindrome 세기
printf("수를 입력하세요: ");
scanf("%d", &N);
for (i = 0; ;i++) {
if (Is_Palindrome(i))
count++;
if (count == N) //개수가 N이면 반복을 멈춘다.
break;
}
printf("%d", i); // 반복문이 멈췄을 때의 i가 우리가 원하는 Palindrome
}
int Is_Palindrome(int num)
{
int i, j; //반복문 변수
int len = 1; //num의 자리수를 결정하는 변수
int arr[MAX]; //Palindrome인지 아닌지 확인할 때 쓰는 배열
int each; //각 자리의 숫자를 나타내는 변수
while (num / len != 0) { //몫이 0일 때 반복문을 멈춘다.
len *= 10;
}
len /= 10; //10을 나누어야 우리가 쓸 수있는 수가 나온다.
for (i=0; len > 0; len /= 10, i++) { //배열에 삽입
each = num / len;
arr[i] = each;
num -= each*len;
}
for (j = 0; j < i;j++) { //Palindrome 인지 아닌지 판별
if (arr[j] != arr[i - 1 - j])
return FALSE;
}
return TRUE;
}
// 앞뒤가 똑같은 번호 - C#
using System;
namespace Samesame
{
class Program
{
static long checker(int n)
{
int check = 0; long i = 0;
while(true)
{
if (check > n)
goto NO;
bool error = false;
string s = i.ToString();
int a = 0, b = s.Length - 1;
for (; a < s.Length / 2; a++, b--)
{
if (s[a] != s[b])
{
error = true;
break;
}
}
if (error == false)
{
check++;
if (check == n)
return i;
}
i++;
}
NO:
return -1;
}
static void Main(string[] args)
{
Console.Write("Ready>>");
int n = int.Parse(Console.ReadLine());
Console.WriteLine(checker(n));
}
}
}
[Python 3.6]
import math
def findNum(numCnt):
if numCnt < 10: return numCnt - 1
numdigi = 1
while True:
if numCnt < calcAddCnt(numdigi): break
numCnt -= calcAddCnt(numdigi)
numdigi += 1
preStr = midStr = ""
if(numdigi % 2):
preStr = str(int(10 ** (math.floor(numdigi / 2) - 1) + (divmod(numCnt, 10))[0]))
midStr = str((divmod(numCnt, 10))[1]-1)
else:
preStr = str(int(10 ** (numdigi / 2 - 1) + (numCnt - 1)))
postStr = list(preStr)
postStr.reverse()
postStr = ''.join(postStr)
return int(preStr + midStr + postStr)
def calcAddCnt(numdigi):
if numdigi == 1: return 10
if numdigi % 2: return calcAddCnt(numdigi - 1) * 10
return 10**math.floor(numdigi / 2) - 10 ** (math.floor(numdigi / 2) - 1)
print(findNum(1))
print(findNum(4))
print(findNum(30))
print(findNum(100))
print(findNum(30000))
print(findNum(1000000))
C#
그냥 계산했는데. 문제에 시간 제한만 붙으면 난이도가 확 뛰겠네요.
using static System.Console;
class Palindrome
{
static bool isPalindrome(int n)
{
string s = n.ToString();
int p = 0, q = s.Length - 1;
while (p <= q)
{
if (s[p] != s[q])
return false;
p++;
q--;
}
return true;
}
static void Main(string[] args)
{
int N = 1;
while (true)
{
Write("N=");
N = int.Parse(ReadLine()); // N >= 1
int cnt = 0;
for (int n = 0; ; n++)
{
if (isPalindrome(n))
{
cnt++;
if (cnt == N)
{
WriteLine(n);
break;
}
}
}
}
}
}
아니면 이렇게.
reverse가 쓰기 좀 어렵네요.
static void Main(string[] args)
{
int N = 1;
while (true)
{
Write("N=");
N = int.Parse(ReadLine()); // N >= 1
int cnt = 0;
for (int n = 0; ; n++)
{
if (n.ToString() == new string(n.ToString().Reverse().ToArray()))
{
cnt++;
if (cnt == N)
{
WriteLine(n);
break;
}
}
}
}
}
def getCnt(n):
idx = 0
num = 0
while True:
if ck(str(num)):
idx += 1
if idx == n:
break
num += 1
print(num)
def ck(str_num):
leng = len(str_num)
if str_num == '' or leng == 1:
return True
leng = leng//2
a1 = str_num[:leng]
a2 = (str_num[-leng:])[::-1]
if a1 == a2:
return True
else:
return False
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _20170827
{
class Program
{
static void Main(string[] args)
{
int b = 0;
int n = int.Parse(Console.ReadLine());
for (int a=0; a<int.MaxValue; a++)
{
string number = a.ToString();
string front = string.Empty;
string back = string.Empty;
if (number.Length == 1)
{
//통과
b = b + 1;
if (b == n)
{
Console.WriteLine(number);
}
continue;
}
if (number.Length % 2 == 0)
{
front = number.Substring(number.Length / 2, number.Length / 2);
back = new string(number.Substring(0, number.Length / 2).ToCharArray().Reverse().ToArray());
}
else
{
front = number.Substring((number.Length / 2) + 1, number.Length / 2);
back = new string(number.Substring(0, (number.Length / 2)).ToCharArray().Reverse().ToArray());
}
if (front == back)
{
b = b + 1;
if(b==n)
{
Console.WriteLine(number);
}
}
}
}
}
}
def symmetric_num(n) :
symmetric_nums = []
i = 0
while True :
if len(symmetric_nums) == n :
break
i_list1 = list(str(i))
i_list2 = list(str(i))
i_list2.reverse()
a = i_list1
b = i_list2
if a == b :
symmetric_nums.append(i)
i += 1
return symmetric_nums[n-1]
자바
public class iiki {
public static void main(String[] agrs)
{
Scanner scan = new Scanner(System.in);
System.out.println("앞뒤가 같은수의 배열을 생성할 최대값:");
int a = scan.nextInt();
//앞뒤가 같은수로 된 배열 생성
List<Integer> list = create_List(a);
System.out.println("앞뒤가 같은수의 찾고자 하는 번째수 입력:");
int b =scan.nextInt();
System.out.println(getNum(list,b ));
}
//앞뒤가 같은 수의 배열 생성
static List<Integer> create_List(int n){
List<Integer> list =new ArrayList<Integer>();
for(int i=0;i<=n; i++){
if(String.valueOf(i).charAt(0)==String.valueOf(i).charAt(String.valueOf(i).length()-1)){
list.add(i);
}
}
return list;
}
// 앞뒤가 같은 수의 n번째 값 반환
static int getNum(List<Integer> list,int n){
return list.get(n-1);
}
}
package codingdojang;
import java.util.Scanner;
public class ex15 {
public static boolean check(int a) {
char b[] = String.valueOf(a).toCharArray();
for(int i=0;i<=b.length/2;i++) {
if(b[i] != b[b.length-1-i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int num = sc.nextInt(); sc.nextLine();
int count = 0;
if(num == 0) {System.out.println();}
for(int i=0; i<2000000000; i++) {
if(check(i)) {
count++;
if(num == count) {
System.out.println(i);
break;
}
}
}
}
}
def mirror(n):
m = str(n)
lenth = len(m)
half = lenth // 2
count = 0
if lenth % 2 == 0:
a = m[:half]
b = m[half:]
br = b[::-1]
if a == br:
count = count + 1
else:
a = m[:half]
b = m[(half+1):]
br = b[::-1]
if a == br:
count = count + 1
return count
n = 30000
count = 0
num = 0
while count < n:
if mirror(num) == 1:
count = count + 1
num = num + 1
elif count == n:
print (num)
break
30000번째 계산하는데 (답:200000003) 280초정도 걸리네요
package mgj.test.java;
import java.util.Scanner;
public class Study1 {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
System.out.println("덧샘 대칭수 구하기 프로그램입니다.");
System.out.print("수를 입력해주세요 :");
int a = 0;
String b = "";
a = scanner.nextInt();
if(a>0) {
b = a+"";
//System.out.println(rs(b));
int c = Integer.parseInt(rs(b));
int tot = a+c;
String tot2 = tot+"";
System.out.println(tot2);
System.out.println(iP(tot2));
if(iP(tot2) == false) {
Test2(tot2);
}
}
}
public static String rs(String s) { // 앞뒤 전환
return (new StringBuffer(s)).reverse().toString();
}
static boolean iP(String s) { // 대칭판별
int n = s.length();
for(int i = 0; i< (n/2); ++i) {
if(s.charAt(i) != s.charAt(n-i-1)) {
return false;
}
}
return true;
}
public static void Test2(String tot2) { // 반복문
do {
if(iP(tot2) == false) {
int a = Integer.parseInt(tot2);
System.out.println(a);
String b = a+"";
int c = Integer.parseInt(rs(b));
System.out.println(c);
int tot = a+c;
tot2 = tot+"";
System.out.println(tot2);
System.out.println(iP(tot2));
}
}while(true);
}
}
간단하게 작성했다가 성능의 한계를 맛봤습니다... 마지막껀 결과가 안나오더군요... 아주 심플하게 1부터 쭉 카운트 해서 뒤집은 숫자랑 같으면 펠린드롬이므로 리턴하는 함수 입니다. 심하게 느려요.
const palindrom = n => {
let result = -1;
for (let i = 1; i <= n; i++) {
do {
result += +1;
} while (result.toString() !== result.toString().split('').reverse().join(''));
}
return result;
};
console.log(palindrom(1));
console.log(palindrom(4));
console.log(palindrom(30));
console.log(palindrom(100));
console.log(palindrom(30000));
console.log(palindrom(1000000));
먼저 펠린드롬의 갯수들을 자릿수 따라서 카운팅 합니다. 카운팅된 숫자만큼은 펠린드롬 계산을 건너 뜁니다. (미약하게 빨라졌군요..) 0~9 까지는 펠린드롬이 10개, 11 ~ 99 까지는 펠린드롬이 9개, (10^0 * 9) 101 ~ 999 까지는 90개 (10^1 * 9) 1001 ~ 9999 까지도 90개 (10^1 * 9) 10001 ~ 99999 까지는 900개 (10^2 * 9) 이런식으로 카운팅 해서 10 몇 번째 자릿수에서 나머지 펠린드롬을 계산해야 하는지 알아냅니다. 마지막으로는 나머지 자릿수에서 펠린드롬을 계산해서 리턴. 짱구를 굴려서 새로 작성했는데 역시나 아직 많이 느리군요 ㅋ 아직 갈길이 멀군요 ㅋㅋ
const newPalindrom = n => {
let palindromCount = 1;
let digit = 1;
let tmp = 0;
while(true) {
tmp = Math.pow(10, Math.ceil(digit / 2) - 1) * 9;
if (n < palindromCount + tmp) {
break;
}
palindromCount += tmp;
digit++;
}
const start = Math.pow(10, Math.ceil(digit / 2) - 1);
const end = Math.pow(10, Math.ceil(digit / 2));
let result = '1';
for (let i = start; n > palindromCount; i++, palindromCount++) {
if (digit % 2) { // odd: 10101 -> 101 + 01
let tmp = i.toString().split('').reverse();
tmp.splice(0, 1);
result = i + tmp.join('');
} else { // even: 1001 -> 10 + 01
result = i + i.toString().split('').reverse().join('');
}
}
return result;
};
console.log(newPalindrom(1));
console.log(newPalindrom(4));
console.log(newPalindrom(30));
console.log(newPalindrom(100));
console.log(newPalindrom(30000));
console.log(newPalindrom(1000000));
def program(x):
lst, i =[] , 0
while x != len(lst):
if list(str(i))[0] == list(str(i))[-1] :
lst.append(i)
i +=1
return(lst[-1])
program(10000)
def program(x):
lst, i =[] , 0
while x != len(lst):
if list(str(i))[0] == list(str(i))[-1] :
lst.append(i)
i +=1
return(lst[-1])
program(10000)
package justPractice;
import java.util.Arrays;
import java.util.Scanner;
public class asdf {
// int형의 input이 들어오면 String으로 바꾼다
public static String toString(int input) {
String inputStr = ""+input+"";
return inputStr;
}
// input숫자가 palindrome인지 판별한다
public static boolean palinCheck(int input) {
boolean result = true;
String inputStr = toString(input);
int size = inputStr.length();
char[] arr = new char[size];
for(int i=0; i<size; i++) {
arr[i] = inputStr.charAt(i);
}
for(int i=0; i<=size/2; i++) {
if(arr[i] == arr[size-1-i])
continue;
else
result=false;
}
if(result == true) {
return true;
}
else {
return false;
}
}
// palindrome 배열에서 해당 index의 수를 return한다
public static int arrayCheck(int index) {
int size = index+1;
int[] arr = new int[size];
for(int i=0;i<size;i++) {
if(i==0) {
arr[i] = 0;
continue;
}
for(int j=arr[i-1]+1;;j++) { // <- j의 값에는 한계가 없다
if(palinCheck(j)==true) {
arr[i]=j;
break; // <- 다음 j값을 찾기 위해 break
}
}
}
System.out.println("current Array: " + Arrays.toString(arr));
System.out.println("Array's " + index + " index: " + arr[index]);
return arr[index];
}
public static void main(String[] args) {
Scanner a = new Scanner(System.in);
int n = a.nextInt();
arrayCheck(n);
}
}
``````{.java}
package justPractice;
import java.util.Arrays;
import java.util.Scanner;
public class asdf {
// int형의 input이 들어오면 String으로 바꾼다
public static String toString(int input) {
String inputStr = ""+input+"";
return inputStr;
}
// input숫자가 palindrome인지 판별한다
public static boolean palinCheck(int input) {
boolean result = true;
String inputStr = toString(input);
int size = inputStr.length();
char[] arr = new char[size];
for(int i=0; i<size; i++) {
arr[i] = inputStr.charAt(i);
}
for(int i=0; i<=size/2; i++) {
if(arr[i] == arr[size-1-i])
continue;
else
result=false;
}
if(result == true) {
return true;
}
else {
return false;
}
}
// palindrome 배열에서 해당 index의 수를 return한다
public static int arrayCheck(int index) {
int size = index+1;
int[] arr = new int[size];
for(int i=0;i<size;i++) {
if(i==0) {
arr[i] = 0;
continue;
}
for(int j=arr[i-1]+1;;j++) { // <- j의 값에는 한계가 없다
if(palinCheck(j)==true) {
arr[i]=j;
break; // <- 다음 j값을 찾기 위해 break
}
}
}
System.out.println("current Array: " + Arrays.toString(arr));
System.out.println("Array's " + index + " index: " + arr[index]);
return arr[index];
}
public static void main(String[] args) {
Scanner a = new Scanner(System.in);
int n = a.nextInt();
arrayCheck(n);
}
}
Java 입니다.
import java.util.Scanner;
public class level_3_mirroring_number {
public static void main(String[] args) {
System.out.println("0부터 시작하여 n 번째로 뒤집어도 같은 숫자를 출력한다. n을 입력하시오.");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
int i = 0;
int sum = 0;
while(true)
{
int count = 0; // 앞, 뒤로 숫자를 비교했을때 같으면 count + 1.
String str = Integer.toString(i); // int형 i를 string형으로 저장. (첫째자리에 0이있으면 int형의 경우에는 뒤집었을때 0이 사라지기 때문.)
int length = str.length(); // 반복문에 사용할 문자열의 길이를 구함.
for(int j = 0; j < length; j++) // 문자열의 길이만큼 반복.
{
if(str.charAt(j) == str.charAt(length - 1 - j)) // 자리 비교.
{
count++; // 앞, 뒤로 숫자를 비교했을때 같으면 count + 1.
if(count == length)
{
sum++; // 앞, 뒤로 숫자를 비교했을때 모두 같으면 sum + 1.
}
}
}
i++; // i의 값을 1 증가 시켜줌.
if(sum == n) // 만약 sum값이 n값과 같으면 str값을 출력.
{
System.out.println(str);
break;
}
}
}
}
파이썬 3.6
"""
일반 루프문을 이용한 코드는 n이 커질수록 결과값을 얻는데까지 걸리는 시간이 늘어납니다.
아래의 코드로 실행시 n에 어떤수를 입력하여도 즉시 결과값을 얻을 수 있습니다.
아이디어>
- 앞뒤가 같은 수와 순번(n)은 아래와 같은 규칙을 갖습니다.
- 두자리 이상의 n이라는 순번이 있고 n번째의 앞뒤가 같은 수 num이 있다면,
num = str (n의 맨처음 수 - 1) + str(n의 두번째 수: 마지막 수) + str(앞의 문자열에서 마지막 숫자를 없애고 뒤집은 수) + str (n의 맨처음수 - 1)
체크포인트 1> n의 맨처음 수가 '1'인 경우 num의 앞뒤는 공백으로 둡니다.(1-1 = 0 이므로)
체크포인트 2> n의 맨처음 수가 '1'일 때 두번째 수가 '0'이면 '9'로 바꿔줍니다.
"""
def main(n):
if len(n) == 1:
num = str(int(n)-1)
else:
head, body = str(int(n[0])-1), list(n[1:])
if n[0] and '0' in n:
for i,value in enumerate(body):
if n[0] == '1' and i == 0 and value == '0':
body[i] = '9'
body_1 = ''.join(body)
body.pop()
body_2 = ''.join(body)[::-1]
else:
body_1 = ''.join(body)
body_2 = ''.join(body)[::-1]
if n[0] == '1':
num = body_1 + body_2
else:
num = head + body_1 + body_2 + head
print("%s => %s"%(n, int(num)))
if __name__ == "__main__":
n = input("n = ")
main(n)
1 => 0
4 => 3
30 => 202
100 => 909
111 => 1111
1111 => 111111
30000 => 200000002
1000000 => 90000000009
r로 풀었습니다.
```{r}
#우선 n자리수에 앞뒤 같은 수가 몇개인지 계산하는 함수를 만듬.
a <- function(n){
if(n==1){
return(10) #1자리수는 10개임.
} else {
if(n==2){
return(9) #2자리수(11~99)는 9개임.
} else {
m <- n%/%2
if(n%%2==1){ #3,5,7,9,...자리수인 경우
return((10**m-10**(m-1)) * a(1))
} else { #4,6,8,10,...자리수인 경우
return(10**m-10**(m-1))
}}}}
#근데 n이 617~619일 때 Inf로 나오고, 620이상이면 NaN이 나옴.
#R의 오류인지 이 함수의 오류인지 확인 못 함. 하지만 617자릿수 미만까진 문제 없을 것으로 봄.
#위 함수a(n)를 이용해서 m번째 앞뒤 같은 수를 출력하는 함수를 만듬.
apdui<-function(m){
if(m<=10){
return(m-1)
}else{
k<-a(1)
i<-2
while(m>k){
k<-k+a(i)
i<-i+1
}
if(i%%2==1){
r<-10**((i-1)/2-1)-1+m-k+a(i-1)
result<-r
c<-trunc(log10(r))
for(h in 1:(c+1)){
result<-paste0(result,r%%10)
r<-r%/%10
}
return(result)
}else{
r1<-(m-k+a(i-1))%/%10+10**((i-2)/2-1)
r2<-((m-k+a(i-1)))%%10-1
result<-paste0(r1, r2)
c<-trunc(log10(r1))
for(h in 1:(c+1)){
result<-paste0(result,r1%%10)
r1<-r1%/%10
}
return(result)
}}}
apdui(1000000)
```
수학 공식으로 풀었습니다.
def palindrome_finder(t):
u = -1
while 1:
u += 1
v = int(t - (1 + 18*(10**(u+1)-1)/(10-1)))
if v < 0:
v += 18*(10**u)
break
print(t, u, v)
if v > 9*10**u:
v -= 9*10**u
v = str(v + (10**u-1))
v = v + "0" * (u+1-len(v))
return v + v[::-1]
else:
v = str(v + (10**u-1))
v = v + "0" * (u+1-len(v))
return v[:-1] + v[::-1]
print(palindrome_finder(1))
print(palindrome_finder(4))
print(palindrome_finder(30))
print(palindrome_finder(100))
print(palindrome_finder(30000))
print(palindrome_finder(1000000))
# t번째 palindrome의 u와 v 값을 구합니다.
# 등비수열 합의 공식 등을 이용합니다.
# ex) u = 2, v = 923이라고 합시다.
# 그렇다면 6자릿수의 24번째 palindrome이 됩니다.
# 6번째 자릿수의 시작은 100001 이며 앞의 절반 숫자는 1 0 0 입니다..
# 24번째의 숫자는 1 2 3 입니다.
# palindrome으로는 "123" + "321"
# 즉 답이 123321 이 됩니다.
# palindrome 0 1 11 111 1001 10001 100001 1000001 10000001
# 자릿수 1 1 2 3 4 5 6 7 8
# u 0 0 0 1 1 2 2 3 3
# 갯수 1 9 9 90 90 900 900 9000 9000
# v = 자기 u 안에서 몇번째인지
import math
def palindrome(n):
b = ''
def renumber(n):
if n > 10:
if str(n) > '1'+'9'*(len(str(n))-1):
return n-1 - int('1'+'9'*(len(str(n))-1)), 2*len(str(n))-1
elif str(n) > '10'+'9'*(len(str(n))-2):
return n-1 - int('10'+'9'*(len(str(n))-2)), 2*len(str(n))-2
else:
return n-1 - int('1'+'9'*(len(str(n))-2)), 2*len(str(n))-3
else:
return n-1, 1
a = renumber(n)
c = math.ceil(a[1]/2)
if a[1]%2 and c > 1:
b += str(a[0]+10**(c-1))
b += str(a[0]+10**(c-1))[-2::-1]
elif not(a[1]%2):
b += str(a[0]+10**(c-1))
b += str(a[0]+10**(c-1))[::-1]
elif a[1] == 1:
b = a[0]
return b
print(palindrome(int(input())))
import java.util.Scanner;
public class num15 {
public static String execute(int num){
long count=0;
int listCount = 0;
String number = null;
while(listCount < num){
boolean flag = true;
String numString = count + "";
int lastDigit = 0;
int firstDigit = numString.length()-1;
while(lastDigit <= firstDigit && flag){
if(numString.charAt(lastDigit) == numString.charAt(firstDigit)){
lastDigit++;
if(firstDigit>0) firstDigit--;
}else{
flag = false;
}
}
if(flag){
listCount++;
number = numString;
}
count++;
}
return number;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(execute(n));
}
}
Swift입니다.
순차적인 방법으로 풀었는데, 30,000번째 숫자를 찾는데 10분 넘게 걸려서 방식을 바꿔서 38초까지 줄였습니다. 그런데, vegan님의 python코드는 엄청나게 빠르네요. 순차적인 방식이 아닌 앞뒤가 같은 숫자를 만들어서 30,000번째를 찾는 방식이 기발합니다. 나중에 그 방식으로 풀어봐야겠네요.
var count = 0
var number = -1
let sw1 = DispatchTime.now()
func add1(index: Int) -> Int {
numbers[index] += 1
if numbers[index] >= 10 {
numbers[index] = 0
return add1(index: index + 1)
} else {
return index
}
}
var numbers = [Int](repeating:0, count:20)
numbers[0] = -1
var maxDigitIndex = 0
while(true) {
let tempmaxDigitIndex = add1(index: 0)
number += 1
maxDigitIndex = tempmaxDigitIndex > maxDigitIndex ? tempmaxDigitIndex : maxDigitIndex
var isSame = true
if number >= 10 {
let loopCount = Int(Double(Double(maxDigitIndex + 1) / 2).rounded(.down))
for i in 0..<loopCount {
if numbers[i] != numbers[maxDigitIndex - i] {
isSame = false
break;
}
}
}
if isSame {
count += 1
if count == 30000 {
print(number)
break
}
}
}
let sw2 = DispatchTime.now()
let elappsed1 = Double(sw2.uptimeNanoseconds - sw1.uptimeNanoseconds) / 1_000_000_000
print ("Elappsed 1 : \(elappsed1) seconds")
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int main() {
int num = 0;
int n = 0;
int m = 0;
int index = 0;
int sol = 0;
int pw = 0;
char ptr[2];
char index1[20];
int sn = 0;
int sn1 = 0;
scanf("%d", &num);
while (sn < num) {
n++;
if (n % 2 == 0) {
sn = ((pow(10.0, (n / 2)) - 1) * 2)+1;
sn1 = ((pow(10.0, (n / 2)-1) - 1) * 2) + 9 * pow(10.0, (n / 2)-1) + 1;
}
else if (n % 2 == 1) {
sn1 = ((pow(10.0, (n / 2)) - 1) * 2) + 1;
sn = ((pow(10.0, (n / 2)) - 1) * 2) + 9 * pow(10.0, (n / 2)) + 1;
}
}
m = n + 1;
index = num - sn1;
sprintf(index1, "%d", index);
if (n % 2 == 0) {
for (int i = 0; i < n/2; i++) {
strncpy(ptr, &index1[i], 1);
pw = pow(10.0, (n/2) - 1);
sol += atoi(ptr)*pow(10.0, (n - 1) - i) + atoi(ptr)*pow(10.0, i);
}
}
else
for (int i = 0; i < m/2; i++) {
strncpy(ptr, &index1[i], 1);
pw = pow(10.0, (m/2) - 1);
if (i != (m / 2) - 1)
sol += atoi(ptr)*pow(10.0, (n - 1) - i) + atoi(ptr)*pow(10.0, i);
else
sol += atoi(ptr)*pow(10.0, (n - 1) - i);
}
printf("%d 번째 수는 %d 자리수의 %d 번째 원소 %d 입니다.",num, n, index, sol);
return 0;
}
1.숫자를 입력받음(앞뒤가 같은수의 번호).
2.수열을 이용해 입력받은 번호와 가장 가까운 n자리수 까지의 개수의 합을 구함.
ex) n = 150일때 3자리 숫자 개수 의 총합 = 1자리수(10개) + 두자리수(9개) + 세자리수 (90개) = 109개
3.입력받은 번호와 n자리 수 까지의 개수의 합을 빼줌, 그 결과값이 n+1자리 수 내에서의 index(배열번호)
ex) 150 - 109 = 41
4.n+1자리 숫자 내에서의 index를 찾는 연산 시작.
ex) n + 1 = 4 이므로 4자리수.
4자리 숫자에서는 1,4번째 자리 수와 2,3번째 자리 수가같음(4114, 5115, 2332 등등..)
1번째 4번째 자리 수는 인덱스의 10의자리수와 같음.
2번째 3번째 자리 수는 인덱스의 1의자리수와 같음.
즉, 인덱스를 거울로 비춘 숫자가 찾고자 하는 숫자.
만약, 인덱스가 5자리 숫자의 411번째라 하면 41114가 될것이고, 6자리 숫자의 415번째라 하면 415514가 될 것임.
시간복잡도를 구해보진 않았지만, O(n)이거나 그이하 일 것이라 생각됩니다.
아직 정리 능력은 떨어져서 코드는 좀 난잡하네요.
/* 앞뒤가 같은 수 */
package main
import (
"fmt"
"strconv"
)
func main() {
fmt.Println(nthPalindrome(1))
fmt.Println(nthPalindrome(4))
fmt.Println(nthPalindrome(30))
fmt.Println(nthPalindrome(100))
fmt.Println(nthPalindrome(30000))
fmt.Println(nthPalindrome(10000000))
}
// nthPalindrome: nth번째 Palindrome 값 반환
func nthPalindrome(nth int) int {
// n이 몇 번째(nDigits) Palindrome 슬라이스에 해당되는 지 계산
nDigits, count := 1, len(Palindrome(1))
for nth > count {
nDigits++
count += len(Palindrome(nDigits))
}
// nDigits-1 번째 Palindrome 까지 개수 카운트
count = 0
for i := 1; i < nDigits; i++ {
count += len(Palindrome(i))
}
// nDigits번째 Palindrome 슬라이스에서 nth에 매칭되는 값 반환
rst, _ := strconv.Atoi(Palindrome(nDigits)[(nth-count)-1])
return rst
}
// Palindrome: nDigits 자리수의 Palindrome 슬라이스 반환(재귀사용)
func Palindrome(nDigits int) []string {
rst := []string{}
switch {
case nDigits == 1:
for i := 0; i < 10; i++ {
rst = append(rst, fmt.Sprint(i))
}
case nDigits%2 == 0:
for _, ve := range Palindrome(nDigits - 1) {
if ve[0:1] != "0" {
half := int(len(ve)/2 + 1)
rst = append(rst, ve[:half]+reverse(ve[:half]))
}
}
case nDigits%2 != 0:
for _, ve := range Palindrome(nDigits - 1) {
for _, v1 := range Palindrome(1) {
half := len(ve) / 2
rst = append(rst, ve[:half]+v1+ve[half:])
}
}
}
return rst
}
func reverse(s string) string {
rst := ""
for idx := 0; idx < len(s); idx++ {
rst = s[idx:idx+1] + rst
}
return rst
}
Python 3입니다
def nthpalin(n):
count = 0
result = []
while len(result) < n:
count = count + 1
result = [x for x in range(count*1000) if str(x) == str(x)[::-1]]
return result[n-1]
수가 커지면 느려지네요
너무 느리네요....
n,x,o,d = int(input("수를 입력하세요")),1,-1,0
while d < n:
o += 1
a = list(str(o))
if a == list(reversed(a)):
answer = o
d += 1
print(answer)
import java.util.ArrayList; class Data {
public static void main(String[] args) {
int n = 100;
ArrayList<Integer> al = new ArrayList<>();
int i = 0;
while (al.size() < n) {
StringBuffer sb = new StringBuffer(String.valueOf(i));
if (sb.toString().equals(sb.reverse().toString())) {
al.add(i);
}
i++;
}
System.out.println(al.get(n - 1));
}
}
def symmetricNum(n):
lst = []
x = 0
while True:
if str(x) == str(x)[::-1]:
lst.append(x)
x += 1
if len(lst) == n+1:
break
else:
x += 1
return lst[-1]
n 크기제한이 없게하려면 다른 방법으로 구현해야 할 듯 합니다. 재귀함수라서 크기가 커지면 stackoverflow가 납니다만 여기까지만 풀이하겠습니다.
/**
* @author Kimseongsu
* @see http://codingdojang.com/scode/401
*
*/
public class P401 {
public static void main(String[] args) {
final long[] INPUT = {1, 4, 30, 100, 30000, 1000000};
for (int i = 0; i<INPUT.length; i++) {
System.out.println(INPUT[i] + " => " + search(INPUT[i], 1, 0));
}
}
/**
* 현재 자릿수(digit)에서 (N-n)번째 숫자를 검색 시도
* @param N 목표 N
* @param digit 현재 검색할 자릿수
* @param n 현재까지의 n
* @return
*/
private static String search(final long N, int digit, long n) {
final boolean isOddDigit = digit % 2 == 1;
final boolean hasMiddleNumber = digit > 1 && isOddDigit;
final boolean hasMirrorNumber = digit > 1;
long prefixSize = getPrefixEnd(digit) - getPrefixStart(digit) + 1;
long totalCountInDigit = prefixSize;
if (hasMiddleNumber) {
totalCountInDigit *= 10;
}
if (n + totalCountInDigit < N) {
// 현재 자릿수에서 못찾으므로, 다음 자릿수에서 다시 검색
return search(N, digit + 1, n + totalCountInDigit);
} else {
// 현재 자릿수에 있음.
if (!hasMiddleNumber) { // 자릿수가 짝수일경우: 가운데 숫자가 없으므로 값 + 역순값 으로 결정
long prefix = getPrefixStart(digit) + (N - n - 1);
String revPrefix = hasMirrorNumber? new StringBuilder(String.valueOf(prefix)).reverse().toString() : "";
return "" + prefix + revPrefix;
} else { // 자릿수가 홀수일 경우: 가운데 숫자가 존재 -> 값 + 가운뎃수 + 역순값 으로 결정
int middle = (int) ((N - n - 1) % 10);
long prefix = getPrefixStart(digit) + (N - n - 1) / 10;
String revPrefix = hasMirrorNumber? new StringBuilder(String.valueOf(prefix)).reverse().toString() : "";
return "" + prefix + middle + revPrefix;
}
}
}
private static long getPrefixStart(int digit) {
if (digit == 1) {
return 0;
}
return (long) Math.pow(10, digit / 2 - 1);
}
private static long getPrefixEnd(int digit) {
if (digit == 1)
return 9;
return (long) Math.pow(10, digit / 2) - 1;
}
}
cnt 를 하나씩 늘리면서 검사하고 맞는 것만 리스트에 넣는 기초적인 방법은 성능면에서 너무 노답이라 그냥 아예 팰린드롬을 직접 만들어서 넣는 방법으로 구현했습니다.
문제는 1- 9 / 10 - 99 / 100 -999 .... 가 각각 두번씩 돌아야 예를 들어 12로 만든 121 와 1221 이 모두 리스트에 들어간다는 거였는데 거기서 좀 애를 먹다가 square라는 변수를 이용해 성공했습니다.
더이상 개선하는 건 역량 부족이라... 우선 속도는 상당히 빠르게 나옵니다.
def frontend(num):
mylist = [0]
cnt = 1
if num ==1 : return 0
square = 0
while True :
while True : # 1-9 / 10 - 99 등 첫번쨰 사이클 (ex. 121)
can1 = str(cnt) + str(cnt)[::-1][1:]
mylist.append(int(can1))
if len(mylist) == num:
return mylist[-1]
if set(list(str(cnt))) == {'9'}:
cnt = 10**square
if len(mylist) == num:
return mylist[-1]
break
cnt += 1
while True : # 1-9 / 10 - 99 등 두번쨰 사이클 (ex.1221)
can2 = str(cnt) + str(cnt)[::-1]
mylist.append(int(can2))
if len(mylist) == num:
return mylist[-1]
if set(list(str(cnt))) == {'9'}:
square += 1
cnt = 10**square
if len(mylist) == num:
return mylist[-1]
break
cnt += 1
print(frontend(1))
print(frontend(4))
print(frontend(30))
print(frontend(100))
print(frontend(30000))
print(frontend(1000000))
def palindrome_number (N):
x = 0
R=[]
while len(R) < N:
y = list (str(x))
r = []
for i in range (0,len(y)/2):
if y[i] == y[-(i+1)]:
r.append('o')
else:
r.append('n')
if 'n' in r:
pass
else:
R.append(x)
x += 1
return R[-1]
class EqualInverseNum {
public boolean isInverseEqual(int num) { // 거꾸로 해도 같은 숫자인지 확인하는 함수
String numStr = String.valueOf(num);// 정수 -> 문자열정수
String[] numStrList = new String[numStr.length()]; // 각 자릿수문자열을 요소로 담은 리스트
String invsnumStr = "";
boolean istrue;
for (int i=0; i < numStr.length() ; i++) { // 각 자릿수를 요소로 갖는 리스트를 채운다.
numStrList[i] = numStr.substring(i, i+1);
}
for (int j=numStrList.length - 1 ; j >=0 ; j--) { // 각 자릿수를 역으로 세며 역으로 된 정수문자열을 만든다.
invsnumStr += numStrList[j];
}
if (num == Integer.parseInt(invsnumStr)) { // 두 정수가 같은지 확인한다.
istrue = true;
}else {
istrue = false;
}
return istrue;
}
public int[] getInvEqualNum(int n) { // n번째 '거꾸로 해도 같은 숫자' 까지의 리스트를 반환하는 함수
int count = 0; // 리스트에 추가될 시 1씩 증가
int[] invEqualNumList = new int[n];
for (int num=0; count < n ; num++) {
if (isInverseEqual(num)) {
invEqualNumList[count] = num;
count++;
}
else {
}
}
return invEqualNumList;
}
public static void main(String[] args) {
EqualInverseNum ein = new EqualInverseNum();
int n = 3000;
int[] resultList = ein.getInvEqualNum(n);
int result = resultList[n-1];
System.out.println("n번째 '거꾸로 해도 같은 숫자' 리스트 : ");
System.out.println(Arrays.toString(resultList));
System.out.println("n번째 '거꾸로 해도 같은 숫자' : " + result);
}
}
Python
jari = 1
max_n = 1000000
ans = []
while len(ans) <= max_n:
if jari == 1:
for i in range(0, 10):
ans.append(str(i))
else:
for i in range(10**(jari//2-1), 10**(jari//2)):
if jari%2 == 0:
ans.append(str(i)+str(i)[::-1])
else:
for j in range(0, 10):
ans.append(str(i)+str(j)+str(i)[::-1])
jari += 1
#print(len(ans))
#if jari == 9:
# break
ans = list(map(int, ans))
#sorted(ans)
print(ans)
test = [1, 4, 30, 100, 30000, 100000]
for t in test:
print(ans[t-1])
import java.io.*;
import java.util.*;
public class Main {
static List<Integer>nums=new ArrayList<Integer>();
static int limit=100000;
static int start=0;
public static void main(String[] args) {
while(true) {
System.out.println("몇 번째 숫자");
Scanner sc=new Scanner(System.in);
int index=sc.nextInt();
while(index>nums.size()) {
for(int i=start;i<limit;i++) {
StringBuilder sb=new StringBuilder(String.valueOf(i));
if(Integer.parseInt(sb.toString())==Integer.parseInt(sb.reverse().toString())) {
nums.add(i);
}
}
start=limit;
limit+=100000;
}
System.out.println(nums.get(index));
}
}
}
아래의 규칙을 이용하면 되지 않을까? 다른 풀이들을 시험해보면 대부분 오래 걸리거나 1 초 이상 걸리는데, 아래 방법으로 100000000000000000000 번째 palindrome 수를 찾을 때도 0.000001 초 이하로 나옴.
0 -> 1 개
1 자리수 -> ( 9 x 10 ** 0 ) 개 (palindrome 수 갯수) (1~9)
2 자리수 -> ( 9 x 10 ** 0 ) 개
3 자리수 -> ( 9 x 10 ** 1 ) 개
4 자리수 -> ( 9 x 10 ** 1 ) 개
5 자리수 -> ( 9 x 10 ** 2 ) 개
6 자리수 -> ( 9 x 10 ** 2 ) 개
7 자리수 -> ( 9 x 10 ** 3 ) 개
8 자리수 -> ( 9 x 10 ** 3 ) 개
...
10 의 승수를 곱하는 함수
f(1) = 0
f(2) = 0
f(3) = 1
f(4) = 1
f(5) = 2
f(6) = 2
...
f(x) = int( (x-1) / 2 )
import sys
from functools import reduce
# input : 숫자의 자릿수 k
# output : k 자릿수의 수 중에서 palindrome 수의 갯수
def getPalinCount( k ):
if k < 1:
return 0
else:
return ( 9 * 10 ** int((k - 1)/2) )
# 1 ~ k 자릿수까지의 palindrome 수의 총 갯수 합
def getPalinSum( k ):
return ( sum( [ getPalinCount(i+1) for i in range(k) ] ) + 1 ) # plus 1 for 0
if __name__ == "__main__":
n = int(sys.argv[1]) # n > 0
if n <= 10:
print("result : {}".format(n-1))
sys.exit(0)
k = 0
sum_palin = 0
# n 번째 palindrome 수가 몇자리 수인지 찾는다.
while sum_palin < n:
k += 1
sum_palin = getPalinSum(k)
print("==> {} 번째 palin 자릿수: {}".format(n,k), end='')
# k 자릿수의 수 중에서 n 번째 palindrome 수를 찾기 위해
# 앞쪽의 수부터 결정하면서 범위를 좁혀나간다.
base_sum = getPalinSum(k-1)
remain_n = n - base_sum
val_str = ""
val_str_r = ""
s = 1 # 맨 앞자리는 0 이 올수 없다.
sump = 0
while k > 0:
interval = int(getPalinCount(k) / 9)
for i in range(s, 10):
sump += interval
if sump >= remain_n:
val_str += str(i)
if k != 1:
val_str_r += str(i)
remain_n = remain_n - (sump - interval)
k = k - 2
s = 0
sump = 0
break
print(", result : {}".format(val_str + val_str_r[::-1]))
파이썬
def reversable(i): # 어느 수가 거꾸로 했을 때 같은 값인지 여부 판단
if i == int(str(i)[::-1]):
return True
else:
return False
def n_th(n):
i = 0
count = 0
while True:
if reversable(i):
count += 1
if n == count:
break
i += 1
return i
print(n_th(30)) #202
네이티브하게 코딩하면 숫자가 커짐에 따라 너무 느려진다
다음과 같이 대칭수를 반으로 쪼개어 나열하여 특정 수열을 만들고, 수열에 따라 n번째 대칭수를 찾게 하였다.
자리수 : 대칭수 앞부분 --- 개수
1 : 0 1 2 3 4 5 6 7 8 9 --- 9 + 1
2 : 1 2 3 4 5 6 7 8 9 --- 9
3 : 10 11 12 13 14 .........98 99 --- 90
4 : 10 11 12 13 ...... 99 --- 90
5 : 100 101 102 ...... 999 --- 900
6 : 100 101 102 ...... 999 --- 900
9 9 90 90 900 900 9000 9000 ..... 9*10^(자리수//2)
def mirror(n):
for i in range(1,n*10):
tmp = sum((9*10**(j//2) for j in range(i)))+1
if tmp >= n: break
r = str(int('9'*(i//2+i%2)) - (tmp-n))
return int(r + r[:i-(i//2+i%2)][::-1])
print('▶ {}'.format(mirror(int(input()))))
100
▶ 909
30000
▶ 200000002
1000000
▶ 90000000009
def is_palindrome(n):
n = str(n)
for i in range(0,int(len(n)/2)):
if(n[i]!=n[-1-i]): return False
return True
print(is_palindrome(1))
n = int(input())
hit = 0
number = 0
while(True):
if is_palindrome(number):
hit+=1
if(n==hit): break
number+=1
print(number)
C#
클래스 주요 메서드:
using System;
using System.Collections.Generic;
using System.Linq;
namespace CD015
{
class Program
{
static void Main(string[] args)
{
Palindrome test;
test = new Palindrome(1);
Console.WriteLine($"{test.Nth} => {test.GetPalindrome}");
test = new Palindrome(4);
Console.WriteLine($"{test.Nth} => {test.GetPalindrome}");
test = new Palindrome(30);
Console.WriteLine($"{test.Nth} => {test.GetPalindrome}");
test = new Palindrome(100);
Console.WriteLine($"{test.Nth} => {test.GetPalindrome}");
test = new Palindrome(30000);
Console.WriteLine($"{test.Nth} => {test.GetPalindrome}");
test = new Palindrome(1000000);
Console.WriteLine($"{test.Nth} => {test.GetPalindrome}");
}
}
class Palindrome
{
public int Nth { get; } // Palindrome 리스트의 Nth 번째 요소
// constructor
public Palindrome(int nth)
{
Nth = nth;
}
// Nth 번째 palindrome number 반환
public string GetPalindrome
{
get
{
int checkPlace = 1;
bool IsOver = false;
while (!IsOver)
{
if (Nth <= GetAccumulatedPalindromeCount(checkPlace))
{
IsOver = true;
}
else
{
checkPlace++;
}
}
// checkPlace: Pow(10, checkPlace-1) 자리수 Palindrome 리스트에 Nth 번쨰 수가 포함됨
int nthInnPlace = Nth - GetAccumulatedPalindromeCount(checkPlace - 1); // 해당 자리수 내 요소 위치
return GeneratenPlacePalindrome(checkPlace)[nthInnPlace - 1];
}
}
// nPlcae 자리수(= Pow(10, nPlace-1))까지의 Palindrome 개수(누적) 반환
// nPlace count accumulative count
// 1(0..9) 10 10
// 2(11..99) 9 19
// 3(101..999) 90 109
// ...
private static int GetAccumulatedPalindromeCount(int nPlace)
{
int result = 0;
if (nPlace == 0)
{
result = 0;
}
else if (nPlace == 1)
{
result = 10;
}
else
{
if (nPlace % 2 == 0)
{
result = GetAccumulatedPalindromeCount(nPlace - 1)
+ 9 * (int)Math.Pow(10, nPlace / 2 - 1);
}
else
{
result = GetAccumulatedPalindromeCount(nPlace - 1)
+ 9 * (int)Math.Pow(10, (nPlace - 1) / 2);
}
}
return result;
}
// nPlace 자리수(= Pow(10, nPlace-1))에 해당하는 Palindrome 리스트<string> 생성
public static List<string> GeneratenPlacePalindrome(int nPlace)
{
List<string> result = new List<string>();
if (nPlace == 1) // 1의 자리 [0..9]
{
result = (from val in Enumerable.Range(0, 10) select val.ToString()).ToList();
}
else
{
if (nPlace % 2 == 0)
{
int startValue = (int)Math.Pow(10, nPlace / 2 - 1);
int count = (int)Math.Pow(10, nPlace / 2) - startValue;
foreach (var val in Enumerable.Range(startValue, count))
{
result.Add(val.ToString() + ReverseNumber(val));
}
}
else
{
int startValue = (int)Math.Pow(10, (nPlace - 1) / 2 - 1);
int count = (int)Math.Pow(10, (nPlace - 1) / 2) - startValue;
foreach (var val in Enumerable.Range(startValue, count))
{
foreach (var midVal in Enumerable.Range(0, 10))
{
result.Add(val.ToString() + midVal.ToString() + ReverseNumber(val));
}
}
}
}
return result;
}
private static string ReverseNumber(int aNumber) // 숫자의 역순 문자열 반환
{
return new string(aNumber.ToString().ToCharArray().Reverse().ToArray());
}
}
}
def det_dec(num):
snum = str(num)
length = len(snum)
snum1 = snum[:(length//2)]
if length%2 == 0:
snum2 = snum[(length//2):]
else:
snum2 = snum[(length//2)+1:]
if snum1 == snum2:
return True
else:
return False
def det_rank():
rank = int(input())
num=0
count=0
while True:
if det_dec(num):
count+=1
if count == rank:
print(num)
break
num+=1
det_rank()
n = int(input("Put nth palindrome you want: "))
pal_list = []
num = 0
def palindrome(num):
if str(num) == str(num)[::-1]:
pal_list.append(num)
while len(pal_list) < n:
palindrome(num)
num += 1
# print(pal_list)
print(pal_list[-1])
앞에분 하신거 참고해서 간단하게 만들어보았습니다.
답은 나오는데 시간이 너무 걸리네요.
Put nth palindrome you want: 30000
200000002
#include "stdafx.h"
#include <iostream>
#include <string>
#include <Windows.h>
using namespace std;
int main(void)
{
int Cnt = 0;
int Num = 0;
size_t idx;
while (1) {
idx = 0;
string str = to_string(Num);
for (idx = 0; idx < str.size() -1 ; idx++) {};
if (str[0] == str[idx]) {
Cnt++;
cout << "Num : " << Num << "," << "Cnt : " << Cnt << endl;
}
Num++;
Sleep(1000);
}
return 0;
}
메서드를 조금 썼네요 ㅎㅎ;;
def check(n):
for i in range(len(str(n))):
if str(n)[len(str(n))-1-i]!=str(n)[i]:
return False
return True
def f(x):
numbers=[]
n=0
while len(numbers) != x:
if check(n):
numbers.append(n)
n+=1
print(numbers[-1])
check(n)으로 n이 회문수인지를 확인하고 f(x)로 x번째 회문수를 구해서 그걸 출력하는 함수입니다
def convert_num(num):
s_num = str(num)
c_s = ''
l = len(s_num)+1
for i in range(1,l):
j = i*-1
c_s = c_s + s_num[j]
#print('num:'+str(num))
#print(' s_num:'+str(s_num))
return int(s_num)-int(c_s)
n = 30
di = 0
i = 0
#aa = []
while True:
if convert_num(di) == 0:
#aa.append(di)
#print('i:'+str(i))
#print(' di:'+str(di))
i = i + 1
if n == i:
print(str(n)+'===>'+str(di))
break
di = di + 1
#print(aa)
필요이상의 값을 구하긴 하지만 하나씩 확인 하는 것보다 속도는 더 빠릅니다.
i <- 1
ct <- 1
pld <- NULL
n <- 100
digit <- 1
while (ct <= n){
if (ct <= 10){
for (j in 0:9){
pld[ct] <- j
ct <- ct + 1
}
} else { #ct > 10
i <- i + 1
du <- i
ct_du <- ct
for (i in (i:10^digit) - 1){
temp <- str_split(i, '')[[1]]
temp_n <- length(temp)
pld[ct] <- as.numeric(paste(temp[1:temp_n], temp[temp_n:1], sep = '', collapse = ''))
ct <- ct + 1
}
for (du in (du:10^digit) - 1){
for (j in 0:9){
temp <- str_split(du, '')[[1]]
temp_n <- length(temp)
pld[ct] <- as.numeric(paste(paste(temp[1:temp_n], collapse = ''), j, paste(temp[temp_n:1], collapse = ''), sep = ''))
ct <- ct + 1
}
}
i <- i + 1
digit <- digit + 1
}
}
print(pld[n])
// 간단하기는 한데... 숫자가 커지면 어마어마하게 느립니다.
import java.util.Scanner;
public class KimSanghyeop
{
public static void main(String[] args)
{
Scanner sc =new Scanner(System.in);
int num =sc.nextInt();
int cnt=0;
long res=0;
String str1, str2;
while(true)
{
str1 = String.valueOf(res);
str2 = new StringBuffer(str1).reverse().toString();
if(str1.equals(str2))
{
cnt+=1;
if(cnt == num)
{
System.out.println("값 : "+res);
break;
}
}
res+=1;
System.out.println(res + " / "+ cnt);
}
System.out.println("종료");
}
}
def check_padindrome(val):
if val == val[::-1]:
return True
return False
in_tgt_cnts = ['1', '4', '30', '100', '30000', '1000000']
for in_tgt_cnt in in_tgt_cnts:
i = pal_cnt = 0
while pal_cnt < int(in_tgt_cnt):
if True == check_padindrome(str(i)):
pal_cnt += 1
if pal_cnt == int(in_tgt_cnt):
break
i += 1
print('{} ==> {}'.format(in_tgt_cnt, i))
test=''
Lists=[]
for j in range(0,200000002+1):
if str(j)[0] != str(j)[-1]:
pass
j=str(j)
for i in reversed(j[len(j)//2:]):
test+=i
if j[:len(j)//2+1] == test or j[:len(j)//2]==test :
Lists.append(j)
test=''
else:test=''
N=int(input('inputs Number: '))
print(Lists[N-1])
너무 오래걸려요..
#include<string>
#include<map>
#include<utility>
#include<iostream>
using namespace std;
int main(void)
{
int button;
cin >> button;
int num = 0;
map<int, string>mp; map<int, string>::iterator mpr;
string s;
int cnt = 0;
for (int i = 0;; i++)
{
s = to_string(i);
for (int i = 0; i < s.length() / 2; i++)
{
if (s[i] == s[s.length() - i - 1])cnt++;
}
if (cnt == s.length() / 2)
{
num++;
mp.insert(make_pair(num, s));
}
if (button == num)break;
cnt = 0;
}
for (mpr = mp.begin(); mpr != mp.end(); mpr++)
{
if (mpr->first == num)
{
cout << mpr->second << endl;
}
}
}
R로 작성하였습니다
function1 = function(input, end = 10000){
reverse = c()
for(num in 0:end){
num.vec = strsplit(as.character(num), "")[[1]]
logic = as.vector(matrix(0, ncol = (length(num.vec) / 2), nrow = 1))
for(i in 1:(length(num.vec) / 2)){
if(num.vec[i] == rev(num.vec)[i]){
logic[i] = 1
}else{
logic[i] = 0
}
}
if(sum(!logic) == 0){
reverse = append(reverse, num)
}
}
return(reverse[input])
}
수가 커지면 코드 실행시간이 확 늘어나 버리네요... 다른 분 답을보고 다른 방식으로 해봐야 할 것 같습니다.
def front_back_same(n):
same_list = []
number = 0
while len(same_list) < n:
number = str(number)
mid_point = len(number)
check, index = 1, 0
while index < mid_point:
if number[index] != number[-(index + 1)]:
check = 0
index += 1
if check:
same_list.append(number)
number = int(number)
number += 1
return same_list[-1]
print(front_back_same(int(input())))
import math
def mirror(num): #앞뒤가 같은 수면 return 하는 함수
count = 0
if num >=1 and num <= 9:
return num
else:
for i in range(0, math.floor(len(str(num)) // 2)): #num을 str로 변환해서 인덱스 절반까지 반복문을 돌려서 숫자가 같은지 확인합니다.
if str(num)[len(str(num)) - 1 - i] == str(num)[i]:
count += 1
else:
pass
if count == math.floor(len(str(num)) // 2):
return num
else:
pass
list = []
limit = int(input('숫자 limit을 입력해주세요'))
th = int(input('몇 번째 숫자를 출력할까요?'))
for i in range(1, limit + 1):
try:
if mirror(i) >= 1:
list.append(mirror(i))
except:
TypeError
print(list[th])
def f(n):
m, k = -1, 0
while k <= n:
m += 1
if str(m) == (str(m))[::-1]:
k += 1 #k는 앞뒤가 같은 수의 번호
return m
def check(m):
a = []
for s in str(m):
a.append(s)
b = a.copy()
a.reverse()
if b == a:
return True
return False
def solution(n):
i=0
m=-1
while i<n:
m+=1
if check(m):
i+=1
return m
코드 n이 작을땐 잘되는데 n을 크게 하니까 속도가 너무 늦어버리네요..
def Same_FB(num):
n = 1000000000000
list = []
for i in range(n):
s_i = str(i)
r = s_i[::-1]
r = int(r)
if i == r:
list.append(i)
result = list[(num-1)]
return result
괴상한 풀이법이지만 시간복잡도를 O(1)까지 줄여보려고 생각을 해봤습니다. 1번째 케이스인 0만 예외처리를 해주었고 나머지는 규칙이 있죠 1자리수 1 2 3 4 5 6 7 8 9 // 9개 2자리수 11 22 33 44 55 66 77 88 99 //9개 3자리수 101 111 121 131 141 151 161 171 181 191 202 212 222 232 242 252 262 272 282 292 ... 909 919 929 939 949 959 969 979 989 999 // 90개 4자리수 90개 따라서 N번째인 수를 가지고 몇 자리수이며, 몇번째 숫자인지 알수있습니다.
N <= 9 + 9 + 90 + 90 + 900 +.900 ...로 증가함을 알 수 있고 N <= (9 + 9) + (90 + 90) + (900 +.900) ...로 생각하면 등차수열의 합 공식을 이용하면 N <= 2*(10^i - 1) 이며 식을 i 기준으로 다시 정리해보면 N/2 + 1 <= 10^i가 됩니다. N-=2는 처음 예외처리해준 0때문에 -1해주었고 방금 위 조건을 만족시키려면 N이 17이던 18이던 2자리수이여야하는데 17은 2자리수, 18은 3자리수로 인식해버립니다 그떄문에 N--을 한번더해준것
사실 수학적으로 계산하지 않았으면 코딩을 좀더 잘할수있을텐데 ....아쉽네여
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main()
{
while(true)
{
int N;
int len;
int idx;
string str;
cin >> N;
if(N == 1){
cout << 0;
//return 0;
continue;
}
N-=2;
// N <= 9 + 9 + 90 + 90 + 900 + 900 + ...
// N <= 18 + 180 + 1800 + ....
// N <= 2 * (10^i - 1)
// N/2 + 1 <= 10^i
len = (int)to_string(N/2 + 1).length();
idx = N - 2*(pow(10, len-1) - 1);
if(idx < 9 * pow(10, len-1))
{
idx += (int)pow(10, len -1);
str = to_string(idx);
for(int i = 10; idx / i > 0 ; i*=10)
{
str += to_string(idx / i % 10);
}
}
else {
idx -= 9 * pow(10, len-1);
idx += (int)pow(10, len -1);
str = to_string(idx);
for(int i = 1; idx / i > 0 ; i*=10)
{
str += to_string(idx / i % 10);
}
}
cout << str;
}
return 0;
}
그냥 생각나는 대로 풀어봤습니다. 그치만 역시 중요한건 성능이겠죠...?ㅠㅠ
#include "pch.h"
#include <iostream>
int CheckPal(int input)
{
int tempInput = input;
int numberPosition[255];
int index;
//split number each char
for (index = 0; tempInput != 0; index++)
{
numberPosition[index] = tempInput % 10;
tempInput = tempInput / 10;
}
// index = number of position
for (int i = 0; i < (index / 2); i++)
{
if (numberPosition[i] == numberPosition[index - 1 - i])
{
}
else
{
return -1; // not palindrom
}
}
return 1; //palindrom
}
int main()
{
int input;
int number = 0;
int cnt = 0;
scanf("%d", &input);
while (1)
{
if (CheckPal(number) == 1)
{
cnt++;
if (cnt == input)
{
break;
}
}
number++;
}
printf("%d", number);
}
def palindrome(n):
if len(n) == 1 or n == '10':
return int(n) - 1
tmp = int(n[:2])
if (tmp >= 11) and (tmp < 20):
return n[1:] + (n[1:])[::-1]
elif tmp == 10:
return '9' + n[2:-1] + (n[2:])[::-1] + '9'
else:
f = str(int(n[0]) - 1)
return f + n[1:-1] + (n[1:])[::-1] + f
print(palindrome(input()))
입력받은 값의 크기에 관계없이 O(1)이 나오도록 반복문을 사용하지 않고, string으로 입력 받았습니다.
def search(k):
target = []
count = 0
while True:
check = len(str(count))//2
s = str(count)
inner_check = 0
for i in range(check):
if s[i] == s[-1-i]:
inner_check += 1
if check == inner_check:
target.append(count)
count += 1
if k == len(target):
break
return target[k-1]
print(search(3000))
import java.util.*;
public class Gesipan {
public static void main(String[] args) {
// TODO Auto-generated method stub
int r=15;//r번째 수 찾기
String[] Number = new String[r];
int i=0;//while에서 쓸 +1씩 증가할 수
String x ="0";//배열에 들어갈 숫자
String imsi="";
while(true) {
for(int q=x.length()-1; q>=0; q--)
{
imsi+=String.valueOf(x.charAt(q));
}
if(imsi.equals(x))
{
Number[i]=x;
imsi="";
i++;
x = Integer.toString((Integer.parseInt(x)+1));
if(i==r)
{
break;
}
}
else
{
imsi="";
x = Integer.toString((Integer.parseInt(x)+1));
}
}
System.out.println(Number[r-1]);
}
}
121475번째부터 int 값 초과해서 그냥 문자열 출력으로 변경했습니다.
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
void makePal(int n, int odd) {
int exp = 0;
while ((int)pow(10, exp) <= n) exp++;
string numbers = to_string(n);
for (int i = 0; i < exp; i++) {
if(odd != 1 || i+1 <exp ) numbers += numbers[exp - i -1 -odd];
}
cout << numbers;
}
void genPalNum(int n) {
if (n <= 10) cout << n - 1;
else if (n <= 20) return makePal(n - 10, 1);
int oddflag = 1;
int level = 1;
int sum = 20;
while (sum + 9 * (int)pow(10, level) <= n)
{
sum += 9 * (int)pow(10, level);
if (oddflag == 1) oddflag = 0;
else oddflag = 1, level++;
}
n = n - sum + (int)pow(10, level);
makePal(n,oddflag);
}
IN = int(input())
numlist=[]
for i in range(IN+1):
numlist.append(int(str(i) + str(i)[::-1]))
numlist.append(int(str(i) + str(i)[::-1][1:]))
numlist = list(set(numlist))
numlist.sort()
print(numlist[IN-1])
n = int(input("input :"))
result, inp, count = [], 0, 1
while len(result) <= n-1 :
num = []
num, num_rev = list(str(inp)), list(str(inp))
num_rev.reverse()
if num == num_rev :
result.append(inp)
inp += 1
print(result[-1])
결과
input :10000 9000009
제 코드도 만 단위 이상은 오래걸리네요 ㅠㅠ
nn = 100-1
arr1 = []
arr2 = []
for i in xrange(100000):
arr1 = [str(x) for x in str(i)]
if int("".join(arr1)) == int(''.join(reversed(arr1))):
arr2.append(i)
print arr2[nn]
파이썬입니다 nn에 입력값 넣으면 되네요
Javascript(ES6)...
`반복문으로 계속 숫자 i 를 증가시켜 palindrome 수인지 검사, 맞다면 count 증가시킴, count 가 n 번째에 달하면 (count == n_th) break 하고 i 출력`;
function palin_a(n_th) {
let [i, count] = [-1, 0];
while(true) {
i++;
if(i.toString() == [...i.toString()].reverse().join('')) { count++; }
if(count == n_th) { break; }
}
console.log(i);
}
palin_a(1); // 0
palin_a(4); // 3
palin_a(30); // 202
palin_a(100); // 909
// palin_a(30000); // 시간이 너무 오래 걸림
// palin_a(1000000); // 시간이 너무 오래 걸림
`n 번째에 따른 palindrome 수가 일정한 규칙성을 보이는 것에 착안하여 계산을 하는 방식, 예를들면...
한자리수 palindrome 의 첫번째 수인 0 의 n_th 는 1
두자리수 palindrome 의 첫번째 수인 11의 n_th 는 11
세자리수 palindrome 의 첫번째 수인 101의 n_th 는 20
네자리수 palindrome 의 첫번째 수인 1001의 n_th 는 110
다섯자리수 palindrome 의 첫번째 수인 10001의 n_th 는 200
여섯자리수 palindrome 의 첫번째 수인 100001의 n_th 는 1100
일곱자리수 palindrome 의 첫번째 수인 1000001의 n_th 는 2000
여덟자리수 palindrome 의 첫번째 수인 10000001의 n_th 는 11000
아홉자리수 palindrome 의 첫번째 수인 100000001의 n_th 는 20000 ...
과 같이 일정한 규칙성을 보임
palindrome 의 자릿수와 해당 자릿수의 첫번째 n_th 를 계속 반환하는 제너레이터 함수를 구현, 입력한 n_th 에 따라 palindrome 수를 계산하여 조합`;
// 제너레이트 함수, [palindrome 자릿수, 첫번째 수의 n_th] 반환
function * gen() {
yield [1, 1];
let [count, n1, n2] = [2, 11, 20];
while(true) {
yield [count, n1];
count++;
n1 = Number(n1.toString() + '0');
yield [count, n2];
count++;
n2 = Number(n2.toString() + '0');
}
}
// n_th 번째 palindrome 수 반환 함수
function palin_b(n_th) {
// 입력한 n_th 를 넘지않으면서 가장 가까운 gen 함수의 결과를 받음
let [digit, base_n] = [0, 0];
for(let v of gen()) {
if(v[1] > n_th) { break; }
[digit, base_n] = [v[0], v[1]];
}
// 결과 계산 및 출력
let result = 0;
if(digit == 1) {
result = n_th - 1;
} else if(digit == 2) {
result = (n_th - 10).toString().repeat(2)
} else {
result = (10 ** (~~(digit / 2)) + n_th - base_n).toString();
result += (digit % 2 == 0) ? [...result].reverse().join('') : [...result].slice(0, -1).reverse().join('');
}
console.log(result);
}
palin_b(1); // 0
palin_b(4); // 3
palin_b(30); // 202
palin_b(100); // 909
palin_b(30000); // 200000002
palin_b(1000000); // 90000000009
Python 3...
def palin_b(n_th):
# 제너레이트 함수, (palindrome 자릿수, 그 첫번째 수의 n_th 반환)
def gen():
yield 1, 1
count, n1, n2 = 2, 11, 20
while True:
yield count, n1
count += 1
n1 = int(str(n1) + '0')
yield count, n2
count += 1
n2 = int(str(n2) + '0')
# 자릿수가 넘어갈 때의 palindrome 자릿수 및 그 때의 첫번째 수의 base_n 반환
digit, base_n = 0, 0
for v in gen():
if v[1] > n_th:
break
digit, base_n = v
# n_th 와 base_n 차이 조정으로 결과 출력
result = 0
if digit == 1:
result = n_th - 1
elif digit == 2:
result = str(n_th - 10) * 2
else:
result = str(10**(digit // 2) + n_th - base_n)
result += result[::-1] if digit % 2 == 0 else result[:-1][::-1]
print(result)
palin_b(1) # 0
palin_b(4) # 3
palin_b(30) # 202
palin_b(100) # 909
palin_b(30000) # 200000002
palin_b(1000000) # 90000000009
def get_decal(num):
is_decal = True
for i in range(len(str(num))//2):
if str(num)[i] != str(num)[-i-1]:
is_decal = False
if is_decal:
return num
def n_th_number(n):
count = 0
num = 0
while True:
if get_decal(num):
count += 1
if count == n-1:
return num
num += 1
print(n_th_number(100))
num=int(input("숫자를 입력하십시오: "))
elst=[]
n=0
while len(elst)<num: #num이하의 대칭수 찾기
if str(n)==str(n)[::-1]:
elst.append(n)
n+=1
print(elst[num-1])
확인해 보니 num에 10000이상을 입력하면 오래 걸리기 시작하네요...
number = int(input("number in order>> "))
tmpLst = [x for x in range(1,9999999)]
cpyLst = []
finLst=[0,0]
for i in tmpLst:
i = str(i)
cpyLst.append(i)
for i in cpyLst:
tmp = i[::-1]
if i == tmp:
finLst.append(i)
print(finLst[number])
너무 느려서 못써먹겠네요...
def array(n):
result_list = []
for i in range(0, 10000):
first = list(''.join(str(i)))
first.reverse() #역순으로 정렬된 리스트
second = list(''.join(str(i))) #정상적인 리스트
if first == second:
result_list.append(i)
return result_list[n-1]
print(array(30))
def palindrome(num):
if num<10:
return 1
else:
Str=str(num)
for i in range(len(Str)):
if Str[i]!=Str[len(Str)-i-1]:
return 0
return 1
list_a=[]
i=0
A = int(input("몇번째?"))
while True:
a=palindrome(i)
if a==1:
list_a.append(i)
i+=1
if len(list_a)==A:
break
print(list_a[A-1])
def f(n):
i = 0
result =[]
while 1:
a = str(i)
b = "".join(reversed(a))
if a == b:
result.append(a)
if len(result) == n:
return a
i += 1
def fbn(in1):
inp, num = 0, 0
while inp != in1:
temp = str(num)
if temp == ''.join(reversed(temp)): inp += 1
num += 1
print('{} => {}'.format(in1, temp))
if __name__ == '__main__':
in1 = 30
fbn(in1)
cc=int(input("몇번째의 앞뒤가 같은 수를 구하고 싶나요?"))
n=0
c=0
while True:
if str(n)[::-1]==str(n):
c+=1
if c==cc:
print(n)
break
n+=1
def same(a):
samenum = ['0',]
lst = []
while len(lst)<= a:
if samenum[-1] == samenum[-1][::-1]:
lst.append(samenum[-1])
samenum.append(str(int(samenum[-1])+1))
else:
samenum.append(str(int(samenum[-1])+1))
return lst[-2]
만 단위를 넘어가니 시간이 좀 걸리네요....
/*
http://codingdojang.com/scode/401?answer_mode=hide
문제
앞뒤가 같은 수는 바로 쓴 값과 거꾸로 쓴 값이 같은 수이다. 다음과 같은 예를 들 수 있다.
1
44
101
2002
8972798
1111111111111
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, ... 과 같이, 0 이상의 앞뒤가 같은 수를 크기 순으로 나열할 때, n 번째 수를 계산하는 프로그램을 작성하라.
n은 1부터 시작하며 크기에는 제한이 없다.
*/
import UIKit
var str = "Hello, playground"
public func solution(n:Int) {
var currentCheckCnt:Int = 0
var currentCnt:Int = 0
while true {
currentCnt += 1
if check(n: currentCnt) {
currentCheckCnt += 1
}
if n == currentCheckCnt {
print("결과 :\(currentCnt)")
break
}
}
}
func check(n:Int) -> Bool {
if n < 10 {
return true
}
var compareStr:String = "\(n)"
var compareStrArray:Array = Array(compareStr)
let startIndex = compareStr.index(compareStr.startIndex, offsetBy: 0)
let endIndex = compareStr.index(startIndex, offsetBy: compareStr.count/2)
let firstHalfCompareStr:String = String(compareStr[startIndex..<endIndex])
let reverseStr:String = String(compareStr.reversed())
let startIndex2 = reverseStr.index(reverseStr.startIndex, offsetBy: 0)
let endIndex2 = reverseStr.index(startIndex, offsetBy: reverseStr.count/2)
let lastHalfCompareStr:String = String(reverseStr[startIndex2..<endIndex2])
if firstHalfCompareStr == lastHalfCompareStr {
return true
}
return false
}
solution(n: 50)
``````{.swift}
/*
http://codingdojang.com/scode/401?answer_mode=hide
문제
앞뒤가 같은 수는 바로 쓴 값과 거꾸로 쓴 값이 같은 수이다. 다음과 같은 예를 들 수 있다.
1
44
101
2002
8972798
1111111111111
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, ... 과 같이, 0 이상의 앞뒤가 같은 수를 크기 순으로 나열할 때, n 번째 수를 계산하는 프로그램을 작성하라.
n은 1부터 시작하며 크기에는 제한이 없다.
*/
import UIKit
var str = "Hello, playground"
public func solution(n:Int) {
var currentCheckCnt:Int = 0
var currentCnt:Int = 0
while true {
currentCnt += 1
if check(n: currentCnt) {
currentCheckCnt += 1
}
if n == currentCheckCnt {
print("결과 :\(currentCnt)")
break
}
}
}
func check(n:Int) -> Bool {
if n < 10 {
return true
}
var compareStr:String = "\(n)"
var compareStrArray:Array = Array(compareStr)
let startIndex = compareStr.index(compareStr.startIndex, offsetBy: 0)
let endIndex = compareStr.index(startIndex, offsetBy: compareStr.count/2)
let firstHalfCompareStr:String = String(compareStr[startIndex..<endIndex])
let reverseStr:String = String(compareStr.reversed())
let startIndex2 = reverseStr.index(reverseStr.startIndex, offsetBy: 0)
let endIndex2 = reverseStr.index(startIndex, offsetBy: reverseStr.count/2)
let lastHalfCompareStr:String = String(reverseStr[startIndex2..<endIndex2])
if firstHalfCompareStr == lastHalfCompareStr {
return true
}
return false
}
solution(n: 50)
a=int(input("Enter a number: "))
def palindrome(n):
L=list()
for i in range(len(str(n))):
L.append(str(n)[i]==str(n)[-(i+1)])
if False in L:
return False
else:
return True
a1=0
while len([i for i in range(a1) if palindrome(i)==True])<a:
a1+=1
print([i for i in range(a1) if palindrome(i)==True][-1])
저도 수가 커지면 굉장히 느려집니다. 조금 더 연구하여 효율적으로 계산되는 방법을 연구해봐야겠습니다.
파이썬 입니다.
"""
n=1 한자리 대칭수 : 9 / 두자리 대칭수 9
n=2 세자리 대칭수 : 90 / 네자리 대칭수 : 90
n=3 다섯자리 대칭수 : 900 / 여섯자리 대칭수 : 900
"""
a = int(input())-1 # 몇번째 수인지를 입력받음
if a==0:
print(0)
else:
n = 1
while a>2*(10**n-1):
n = n+1
if a>2*(10**n-1)-9*10**(n-1): ##짝수자리 대칭수
k=2*n
reft = a-(2*(10**(n-1)-1)+9*10**(n-1))
else: # 홀수자리 대칭수
k=2*n-1
reft = a-2*(10**(n-1)-1)
### k자리 대칭수가 됨
''' print(n) print(k) print(reft) k자리 대칭수중 reft번째 수'''
if k%2==1:
atom = int(10**((k-1)/2)+reft-1)
lista = list(str(atom))
listb = list(reversed(lista))
number = 0
del listb[0]
ia = len(lista)
ib = len(listb)
for i in range (0,ia):
number = number + int(lista[i])*10**(ia+ib-i-1)
for i in range (0,ib):
number = number + int(listb[i])*10**(ib-i-1)
print(number)
else:
atom = int(10**((k/2-1)+reft-1))
lista = list(str(atom))
listb = list(reversed(lista))
number = 0
ia = len(lista)
ib = len(listb)
for i in range (0,ia):
number = number + int(lista[i])*10**(ia+ib-i-1)
for i in range (0,ib):
number = number + int(listb[i])*10**(ib-i-1)
print(number)
파이썬 3.7.2 버전입니다.
def foo(X):
num = 0 # 0부터 시작할 숫자 변수
result_counter = 0 # 앞뒤가 같은 숫자를 카운트하는 변수
while True:
if str(num) == str(num)[::-1]:
result_counter += 1
if result_counter == int(X):
return num
num += 1
X = input('앞뒤가 같은 수들의 집합입니다. 몇번째 숫자를 원하십니까? : ')
result = foo(int(X))
print(f'{X}번째 앞뒤가 같은 수 => {result}')
def same(n):
i = 0
result = []
while 1:
if str(i) == str(i)[::-1]:
result.append(i)
if len(result) == n:
print(result[n-1])
break
i += 1
same(1)
same(4)
same(30)
same(100)
1001 이런 것들을 sprintf를 써서 배열 안에 넣고 앞 뒤 검사하면서 맞으면 vector 안에 넣고 아니면 안 넣고라는 식으로 진행하였습니다.
LEN의 값에 따라서 속도가 나뉘는데 Calculation completed 라는 문구가 나오면 for문 안의 계산이 끝났다는 것입니다.
1000000(백만) 정도는 빠르게 계산하는데 그 뒤부터는 약간 시간이 걸리는 듯 합니다.
이후 알고르즘을 개선하여 한번 더 올리도록 하겠습니다.
(다른 분들꺼보니 palindrome을 제작하는 알고리즘을 하셨던데 참고하겠습니다.)
#include <iostream>
#include <cstdio>
#include <vector>
#define LEN 1000000
using namespace std;
bool is_pal(int);
void find(int);
void push(int);
vector<int>ppal;
char num[LEN];
int main() {
int num;
for(int i =0;i<LEN;i++) {
num =i;
if(is_pal(num)) {
push(num);
}
}
cout << "Calculation completed" << endl;
int n;
cin >> n;
find(n-1);
return 0;
}
bool is_pal(const int _num) {
int count=0;
int __num=_num;
while (__num) {
__num/=10;
count++;
}
sprintf(num, "%d", _num);
for(int i =0;i<count/2;i++) {
if(num[i]!=num[count-1-i]) {
return false;
}
}
return true;
}
void push(const int _num) {
ppal.push_back(_num);
}
void find(int n) {
cout << ppal[n] << endl;
}
def palindromic_n(n):
palindromic_list=[]
integer=0
while True:
if list(str(integer))==list(str(integer))[::-1]:
palindromic_list.append(integer)
integer+=1
if len(palindromic_list)==n:
print(palindromic_list[n-1])
break
palindromic_n(30000)
파이썬 3.9.1입니다. 입력된 숫자랑 그 숫자까지 나오는 앞뒤가 같은 수가 모두 출력 되도록 코드를 짰습니다. 하나씩 숫자를 늘려가면서 확인 하는 방법은 너무 느릴것 같아서 앞뒤가 같은 숫자를 만들어서 리스트에 집어 넣는 방법으로 하였습니다. makeSymmetric은 앞뒤가 같은 숫자를 만드는 함수고, symmetric은 만들어진 숫자를 list에 저장하는 함수입니다.
import math
print("숫자를 입력하세요")
n = int(input())
def makeSymmetric(digit, num):
x = '0'* (math.ceil(digit/2) - len(str(num))) + str(num)
if digit == 1:
return str(num)
elif digit % 2 == 0:
return str(x) + ''.join(reversed(str(x)))
elif digit % 2 == 1:
return str(x)[:-1] + ''.join(reversed(str(x)))
def symmetric(n):
symmetrics = ['0']
symmetric = ''
digit = 1
num = 1
while True:
while num < pow(10, math.ceil(digit/2)):
symmetric = makeSymmetric(digit,num)
if not symmetric[0] == '0': symmetrics.append(symmetric)
num += 1
if len(symmetrics) == n: return symmetrics
num = 1
digit += 1
x = symmetric(n)
print(x[-1])
print(x)
python 3.9.1
def palmaker(enum):
temp2 = []
power = len(str(enum[len(enum) - 1])) + 1
for j in range(1, 10):
temp = []
for i in range(0, len(enum)):
temp.append(pow(10, int((power - len(str(enum[i])) + 1) / 2)) * enum[i] + j * (pow(10, power) + 1))
temp2.extend(temp)
enum.extend(temp2)
return enum
def pal(n, num, num2):
temp = []
while n > len(num) + len(num2):
num = palmaker(num)
num2 = palmaker(num2)
temp = num + num2
temp.sort()
return temp[n]
n = 1000000
pal_1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
pal_2 = [0, 11, 22, 33, 44, 55, 66, 77, 88, 99]
print(pal(n, pal_1, pal_2))
회문을 만들 때 앞에서 구한 회문에서 맨 앞과 뒤에 같은 숫자를 붙여 나가는 방식을 이용했습니다.
예를 들어 11이 있다면 앞뒤에 1을 붙여 1111을 만드는 방식입니다.
다만 그냥 해서는 1001과 같이 가운데 0이 들어가는 숫자를 처리할 수 없기 때문에 두 시드에 모두 0을 넣어 주었습니다.
그리고 자릿수에 따라 다른 다른 수가 곱해지도록 했는데
예를 들어 7을 이용해 5자리 회문을 만들 때는 100을 곱하고 10001을 더해 10701을 만들지만
121을 이용해 5자리 회문을 만들 때는 10을 곱하고 10001을 더합니다.
1백만 넣어도 2초정도면 나옵니다.
n = 1 #반복 횟수
lcn = [0] #찾는 수 리스트
input_number = int(input("enter n :"))
inum = 1 #대입해볼 수
while True :
if n == input_number:
break
# inum 리스트로 만들고 거꾸로
lnum = list()
for i in str(inum):
lnum.append(i)
lnum.reverse()
#각 항목을 str으로 변환
lnum = list(map(str,lnum))
#join()이용해서 str으로 결합 후 int로 재변경
irnum = int(''.join(lnum))
#뒤집기 전과 비교
if inum == irnum:
lcn.append(inum)
# debug print(lcn)
n = len(lcn)
inum += 1
print(lcn[input_number-1])
def SameGame(num):
q=[]
for i in range(10000):
if i<10:
q.append(i)
elif len(str(i))%2==0:
e=0
for w in range(len(str(i))):
if str(i)[w]==str(i)[len(str(i))-1-w]:
e+=1
if e==len(str(i)):
q.append(i)
elif len(str(i))%2==1:
e=0
for e in range(len(str(i))):
if str(i)[e]==str(i)[len(str(i))-1-e]:
e+=1
if e==len(str(i)):
q.append(i)
print(q[num-1])
SameGame(100)
def palindrome(n):
"""앞뒤가 같은 수 구하기"""
temp = [x for x in str(n)]
result = []
if temp == list(reversed(temp)):
result.append(n)
print(result, end='')
num = int(input('수를 입력하세요.: '))
for k in range(1, num+1):
palindrome(k)
def next_to_x(x):
list_x=list(str(x))
len_x=len(list_x)
if len_x%2==0: #x의 길이에 따라서 '가운데' 숫자의 index를 돌려주는 변수 middle_num
middle_numx=int((len_x)/2-1)
else:
middle_numx=int((len_x+1)/2-1)
if int(list_x[middle_numx])<9:#그 가운데 indexed num이 9보다 작을 때 새로운 다음 숫자 돌려주는 변수 next_x
i=0
if len_x%2==0:
next_x=''.join(list_x[:middle_numx])
next_x+=str(int(list_x[middle_numx])+1)
next_x+=str(int(list_x[middle_numx])+1)
next_x+=''.join(list_x[middle_numx+2:])
return int(next_x)
else:
next_x=''.join(list_x[0:middle_numx])
next_x+=str(int(list_x[middle_numx])+1)
next_x+=''.join(list_x[middle_numx+1:])
return int(next_x)
elif int(list_x[middle_numx])==9:
i=0
if middle_numx>0 and set(list_x) != {'9'}:
while int(list_x[middle_numx])==9:
# while middle_numx>0:
middle_numx-=1
#i= the number of continuous 9's in the middle
i+=1
next_x=''.join(list_x[:middle_numx])
next_x+=str(int(list_x[middle_numx])+1)
if len_x%2==0:
next_x+=(i*2)*'0'
else:
next_x+=(i*2-1)*'0'
next_x+=str(int(list_x[middle_numx])+1)
# list_x[middle_numx]=int(list_x[middle_numx])+1
if middle_numx>=1:
t=-middle_numx
elif middle_numx==0:
t=len_x
next_x+=''.join(list_x[t:])
return int(next_x)
elif set(list_x)=={'9'}:
next_x='1'+'0'*(len_x-1)+'1'
return int(next_x)
def nth_sym_num(n):
if n==1:
return 1
else:
return(next_to_x(nth_sym_num(n-1)))
# print(next_to_x(101))
# print(next_to_x(99))
# print(next_to_x(1991))
print(nth_sym_num(109))
9로만 이루어진 대칭수와 중간부분에 9가 있는 경우가 힘들었습니다.
우선 next_to_x함수는 주어진 대칭수에 대하여,
그것보다 바로 큰 다음 대칭수를 불러오는 함수입니다!
대칭수 abcdcba 가 있다고 할 때, 이ㅣ d에 +1을 하는 함수가 바로 그 원하는 함수가 됩니다!
(짝수라면 d가 두개겠지요)
다만 이때 가운데 수가 9라면 이를 좌우로 spread해줘야 했는데 그 작업이 어려웠습니다.
하나씩 대입하여 비교하는 방법입니다. 짧지만 n이 커질수록 속도가 확연히 느려집니다
i=int(input())
result=[]
k=0
while len(result)<i:
if str(k)==str(k)[::-1]:
result.append(k)
k+=1
print(k-1)
package justStudying;
public class test2_20210822 {
public static String sol(int n) {
String ans = "";
int cnt = 0;
StringBuffer sb = new StringBuffer("0");
int num = 0;
while(cnt < n) {
// System.out.println(sb.toString() + " cnt = [" + cnt + "]");
if(sb.toString().equals(sb.reverse().toString())) {
cnt++;
if(cnt == n) break;
}
sb.reverse();
num = Integer.parseInt(sb.toString()) + 1;
sb = new StringBuffer(Integer.toString(num));
}
ans = sb.toString();
return ans;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(sol(1000));
}
}
import java.util.Scanner;
public class no1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int result = 0;
for (int i = 0; i < n; result++) {
String number = Integer.toString(result);
if (number.equals(new StringBuilder(number).reverse().toString())) {
i++;
}
}
System.out.println(result - 1);
}
}
n=int(input('숫자를 입력하세요:'))
A=0
count=0
while True:
if str(A)==str(A)[::-1]:
count+=1
if count==n:
break
A+=1
print(A)
a = int(input())
i = 0
b = []
while True:
if str(i) == str(i)[::-1]:
b.append(i)
i += 1
if len(b) == a:
break
b[a-1]
x = 0
Num = []
N = int(input('자연수 n을 입력하시오.'))
print()
while len(Num) != N:
if str(x) == str(x)[::-1]:
Num.append(x)
x += 1
print(Num[-1])
// Rust
// n=1일때 처리는 생략...
fn symmetric_num(n: u32) {
let mut k = 1; // m 자리 그룹의 첫 번째 인덱스
let mut k_prev = k;
let mut m = 0; // m 자리수
while k < n - 1 {
m += 1;
k_prev = k;
k += if m % 2 == 0 { 9 * 10u32.pow(m/2 - 1)}
else { 9 * 10u32.pow((m-1)/2)};
}
let (mut d, mut idx) = subindex(n-1, k_prev, m);
d += 1;
let mut result = vec![d];
let mut i = 1;
while m >= 1 + 2 * i {
d = subindex(idx, 0, m-2*i).0;
idx = subindex(idx, 0, m-2*i).1;
result.push(d);
i += 1;
}
let sym: Vec<&u32> = if m % 2 == 0 { result.iter().rev().collect()}
else { result[..(result.len()-1)].iter().rev().collect()};
println!("{:?}{:?}", result, sym);
}
fn subindex(n: u32, k: u32, m: u32) -> (u32, u32) {
let d = (n - k) / if m%2==0 { 10u32.pow(m/2-1)}
else { 10u32.pow((m-1)/2)};
let idx = (n - k) % if m%2==0 { 10u32.pow(m/2-1)}
else { 10u32.pow((m-1)/2)};
(d, idx)
}
def sol (arr):
a = []
for i in range(10):
for k in arr:
m=str(i)+str(k)+str(i)
a.append(m)
return a
def eliminate(arr):
result=[]
for i in arr:
a=i.strip('0')
if a==i:
result.append(i)
return result
def solution (n):
arr = []
arr1 = [str(i) for i in range(10)]
arr2 = [str(i)*2 for i in range(10)]
arr.extend(arr1)
arr.extend(arr2)
arr.remove('00')
while len(arr)<n:
arr1=sol(arr1)
arr.extend(eliminate(arr1))
arr2=sol(arr2)
arr.extend(eliminate(arr2))
return arr[n-1]
print(solution(1000000))
0~9까지 증가시키고, 양옆으로 동일하게 0~9로 숫자를 증가시켜 str 형태로 이어 붙이는 방식으로 짜봤어요~ 중간에 009900 식으로 양 끝이 '0'으로 잡히는 수들은 eliminate 함수를 둬서, 중간중간 짤라내서 속도를 좀더 높혀봤습니다
package org.javaturotials.ex;
import java.util.*;
public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int count = 0;
int i=0;
int pnum=0;
while(true) {
String is = String.valueOf(i);
StringBuffer bu = new StringBuffer(is);
String ri = bu.reverse().toString();
int a = Integer.valueOf(is);
int b = Integer.valueOf(ri);
if(a==b) {
count++;
pnum=a;
}
i++;
if(count==num) break;
}
System.out.print(pnum);
}
}
n=1000000
def findnum(n):
pnl = [] # palindromic number list
cnt = 0 #자리수 count
while len(pnl) < n:
cnt = cnt +1
if cnt == 1:
pnl.extend([x for x in range(10**cnt)])
elif cnt%2 == 0:
pnl.extend([int(str(x)+str(x)[::-1]) for x in range(10**int((cnt/2-1)),10**int(cnt/2))])
else:
pnl.extend(int(str(x)+str(y)+str(x)[::-1]) for x in range(10**int((cnt/2-1)),10**int(cnt/2)) for y in range(10))
pnl.sort()
return pnl[n-1]
findnum(n)
rev=[0]
n=input()
a=0
while len(rev)<=int(n)-1:
a+=1
a_1=[s for s in str(a)]
a_2=[s for s in str(a)]
a_2.reverse()
if a_1==a_2:
rev.append(a)
else:
pass
print(rev[int(n)-1])
def front_back_same(order):
result = [0]
num = 1
while len(result) != order:
num_str = [int(i) for i in str(num)]
count = 0
for j in range(round(len(num_str) / 2)):
if num_str[j] != num_str[-j-1]: break
count += 1
if count == round(len(num_str) / 2): result += [num]
num += 1
return result[-1]
print('0 이상의 앞뒤가 같은 수를 크기 순으로 나열할 때, n 번째 수를 계산하는 프로그램입니다.')
num = input('구하고 싶은 순서는 몇번째 입니까? : ')
print(front_back_same(int(num)))
10000 이후 부터 속도가 현저히 느려져서, 새로운 방법을 생각해봐야겠습니다.
def palindrome(n):
running = True
number = 1
lst = [0,]
while running:
if n == len(lst):
print(lst[n-1])
running = False
if str(number) == str(number)[::-1]:
lst.append(number)
number += 1
else:
number += 1
palindrome(30) #202 출력
이번 문제 재밌게 풀었습니다~!
n=int(input("#"))
j=0
i=0
while i<n:
li=[]
li1=[]
for k in str(j):
li.append(k)
for k in str(j)[::-1]:
li1.append(k)
if li==li1:
i+=1
j+=1
for i in li:
print(i,end="")
n=int(input("#"))
s=""
s1=""
for i in str(n):
s+=i
for i in str(n)[-1::-1]:
s1+=i
if s==s1:
print("yes")
n = int(input())
i = 0
list1 = [0]
while len(list1) <= n :
num = list(k for k in str(i))
num2 = list(num[i] for i in range(len(num)-1, -1, -1))
if num == num2 :
list1.append(i)
i += 1
print(list1[-1])
자바로 풀어보았습니다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class FindTheNumber {
public static void main(String[] args) {
ArrayList<Integer> specialNumbers = new ArrayList<>(Arrays.asList(0));
ArrayList<Integer> storage = new ArrayList<>();
Scanner scan = new Scanner(System.in);
System.out.println("자연수 N을 입력하시오:");
int N = scan.nextInt();
int number=1, copyNumber;
int count=0, countSame=0, m, n;
while(specialNumbers.size()<N) {
// 자리수 체크
copyNumber = number;
while(copyNumber != 0) {
count++;
copyNumber /= 10;
}
// 자리수가 하나일 경우
if(count==1) {
specialNumbers.add(number);
}else { // 자리수가 2개 이상일 경우
copyNumber = number;
// 각 자리의 숫자를 뽑아서 리스트에 임시 저장
while(copyNumber>0) {
storage.add(copyNumber%10);
copyNumber /= 10;
}
// 대응되는 위치의 숫자들 비교
for(int j=0; j<=(count/2)-1; j++) {
m = storage.get(j);
n = storage.get(count-1-j);
if(m==n) {
countSame+=1;
}
}
// 앞뒤가 같은 숫자인지 판단
if(countSame==count/2) {
specialNumbers.add(number);
}
// 초기화
storage.clear();
countSame=0;
}
// 초기화
number++;
count=0;
}
// 결과 출력
System.out.printf("\n결과 : %d\n", specialNumbers.get(N-1));
}
}
aa = int(input('몇번째를 출력할까요? : '))
bb = [0]
for ii in range(1, aa):
a = str(ii)
b = list(a)
b1 = b[0:-1]
b.reverse()
b1.reverse()
c = ''
for i in b:
c += i
bb.append(int(a + c))
c = ''
for i1 in b1:
c += i1
bb.append(int(a + c))
bb = sorted(bb)
print(bb[aa - 1])
# 015 : 앞뒤가 같은 수
n = int(input())
x = 0
number = 0
while True:
string = str(number)
if string == string[::-1]:
x += 1
if x == n:
print(number)
break
else:
number += 1
풀이 중 가장 간단하게 작성해봤네요. n을 0부터 해서 쭉 앞자리와 뒷자리가 같은 수를 조사하면서 같을 때마다 1씩 더해서 그 수가 SameNumber라는 함수의 매개변수 k와 같으면 n을 출력하는 것으로 해봤습니다
def SameNumber(k):
n = 0
x = 0
while n>=0:
n = str(n)
if n[0] == n[-1]:
x += 1
if k == x:
break
n = int(n)
n += 1
return n
print(SameNumber(100))
num=[]
n=int(input('n?'))
i=0
jari=1
while(True):
temp=str(i)[:(len(str(i))-1)]
re_temp=''
for k in temp:
re_temp=k+re_temp
temp=str(i)+re_temp
if int(temp) not in num:
num.append(int(temp))
temp=str(i)
re_temp=''
for k in temp:
re_temp=k+re_temp
temp=temp+re_temp
if int(temp) not in num:
num.append(int(temp))
i+=1
if len(str(i))>jari:
num.sort()
jari+=1
if len(num)>=n:
print ('%d => %d' %(n,num[n-1]))
break
N = int(input())
n = 0
m= 0
while True:
str_n = str(n)
if str_n[0] == str_n[-1]:
m+=1
if m==N:
print(n)
break
n+=1
def is_mirror(num):
i_list = list(str(num))
i_len = len(i_list)
list_a = i_list[:i_len // 2]
list_b = i_list[i_len // 2 + i_len % 2:]
list_b.reverse()
if list_a == list_b:
return True
else:
return False
n = int(input())
count = 0
i = 0
while count != n:
if is_mirror(i):
count += 1
i += 1
print(i - 1)
def digits_mirror(digits): # digits 자리 수인 앞뒤가 같은 수의 개수를 return
if digits == 1:
count_mirror = 10
else:
if digits % 2 == 0:
count_mirror = 9 * (10 ** (digits // 2 - 1))
print('even', count_mirror, sep='')
else:
count_mirror = 9 * (10 ** (digits // 2 - 1)) * 10
print('odd', count_mirror, sep='')
return count_mirror
def is_mirror(num):
i_list = list(str(num))
i_list_rev = i_list.copy()
i_list_rev.reverse()
# list_a = i_list[:i_len // 2]
# list_b = i_list[i_len // 2 + i_len % 2:]
# list_b.reverse()
return i_list == i_list_rev
n = int(input()) # n번째 앞뒤 같은 수의 개수를 계산해야 함
count = 0 # 앞뒤 같은 수의 개수
next_count = digits_mirror(1)
i = 1 # n번째 앞뒤가 같은 수의 자리 수
while next_count < n:
count = next_count
i += 1
next_count += digits_mirror(i)
print('pre-calc:', count, i)
n_mirror = 10 ** (i - 1) # 앞뒤가 같은 수일지 보는 숫자
while count != n:
if is_mirror(n_mirror):
count += 1
n_mirror += 1
print("ANS: " + str(n_mirror - 1))
def digits_mirror(digits): # digits 자리 수인 앞뒤가 같은 수의 개수를 return
if digits == 1:
count_mirror = 10
else:
if digits % 2 == 0:
count_mirror = 9 * (10 ** (digits // 2 - 1))
else:
count_mirror = 9 * (10 ** (digits // 2 - 1)) * 10
return count_mirror
n = int(input()) # n번째 앞뒤 같은 수의 개수를 계산해야 함
count = 0 # 앞뒤 같은 수의 개수
next_count = digits_mirror(1)
i = 1 # n번째 앞뒤가 같은 수의 자리 수
while next_count < n:
count = next_count
i += 1
next_count += digits_mirror(i)
if i == 1:
print(n - 1)
elif i == 2:
print(11 * (n - count))
elif i % 2 == 0:
print_str = str(10 ** (i // 2 - 1) + (n - count - 1))
print(print_str, end='')
print(print_str[-2::-1])
else:
print_str = str((10 ** (i//2)) + (n - count - 1))
print(print_str, end='')
print(print_str[-2::-1])
def getNum(jari, n):
a = [1]
while jari > 2:
if n > 10**(jari//2):
a[-1] += 1
n -= 10**(jari//2)
else:
a.append(0)
jari -= 2
su = 0
for i in range(len(a)-1):
su = su*10 + a[i]
if jari==2:
su = su*100 + n*10 + n
else:
su = su*10 + n-1
for j in range(len(a)-2,-1,-1):
su = su*10 + a[j]
return su
n = int(input('n 번째 수 >>> '))
if n <= 10:
print(" %d" %(n-1))
else:
n -= 1
jari = 1
while n > 9*(10**(jari//2)):
n -= 9*(10**(jari//2))
if n > 9*(10**(jari//2)):
n -= 9*(10**(jari//2))
jari += 2
else:
jari += 1
break
print(getNum(jari, n))
def sho(num):
return str(num) == str(num)[::-1]
def sol(n):
count = 0
num = 0
while True:
if sho(num):
count += 1
if count == n:
return num
num += 1
n = int(input())
result = sol(n)
print(result)
args에 n 입력 후 실행
package 앞뒤가_같은_수;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Palindrome {
public static void main(String[] args) {
// TODO Auto-generated method stub
final int limit = Integer.parseInt(args[0]);
List<Integer> palList = new ArrayList<Integer>();
int count = 0;
while(palList.size() < limit) {
if(isPalindrome(count)) {
palList.add(count);
}
else {
}
count++;
}
Collections.sort(palList);
System.out.println(palList.get(limit-1));
}
static boolean isPalindrome(int num) {
String numStr = Integer.toString(num);
StringBuffer sb = new StringBuffer();
sb.append(numStr);
sb.reverse();
return sb.toString().equals(numStr);
}
}