읽고 말하기 수열은 다음과 같이 시작하는 수열이다. (Look-and-say sequence라고도 한다)
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...
이 수열은 다음과 같이 앞의 수를 연속된 같은 수의 개수로 묶어서 읽는 방식으로 만들어진다.
- 1을 "1개의 1"로 읽는다: 11
- 11을 "2개의 1"로 읽는다: 21
- 21을 "1개의 2와, 1개의 1"로 읽는다: 1211
- 1211을 "1개의 1과, 1개의 2와, 2개의 1"로 읽는다: 111221
- 111221을 "3개의 1과, 2개의 2와, 1개의 1"로 읽는다: 312211
100번째 수열의 100번째 숫자를 구하라.
(도전과제 1 : 1000번째 수열의 1000번째 숫자를 구하라.)
(도전과제 2 : 100만번째 수열의 100만번째 숫자를 구하라.)
100번째 수열의 100번째 수는 1, 1000번째 수열의 1000번째 수는 3, 100만번째 수열의 100만번째 수는 1이다.
26개의 풀이가 있습니다.
개미수열의 임의의 항 내의 연속된 숫자는 [개수][숫자]의 조합으로 정리됩니다. 이렇게 정리되는 마디(?)들을 볼 때, 앞 마디의 [숫자]와 현 마디의 [개수]가 같거나, 현마디의 [숫자]와 뒷마디의 [개수]가 같은 식으로 같은 숫자는 최대 3번까지만 나올 수 있습니다.
따라서 N 항의 N 자리를 구하고자 할 때는 전체 값을 다 계산하지 않고, 넉넉잡아 N * 3 자리까지만 계산하는 것으로 합니다. Swift 입니다.
func lookAndSay(_ arr: [Int]) -> [Int] {
func helper(_ i:Int) -> (value: Int, length: Int, next: Int) {
let value = arr[i]
var j = i + 1
while j < arr.count && arr[j] == value {
j += 1
}
return (value: value, length: j - i, next: j)
}
var i = 0
var result = [Int]()
while true {
let temp = helper(i)
result += [temp.length, temp.value]
if temp.next >= arr.count || temp.next > 3000 {
return result
}
i = temp.next
}
}
var a = [1]
for i in 1...999 {
a = lookAndSay(a)
}
print(a[999])
Haskell
import Data.List
let ant = iterate (concatMap(\g-> [length g, head g]) . group)[1]
ant !! 99 !! 99
ant !! 999 !! 999
ant !! 999999 !! 999999
Ruby
ant = ->seq=[1] { seq.chunk{|_|_}.flat_map {|h,g|[g.size,h]} }
iterate = ->n { n==1? [1].lazy : ant[iterate[n-1]] }
ant_seq = ->nth,n { puts iterate[100].take(100).force.last }
ant_seq[100,100] #=> "1"
Haskell:
import Data.List (group)
import Control.Monad ((>=>))
import System.Environment (getArgs)
ant = iterate (group >=> sequence[length, head]) [1]
main = do
args <- getArgs
let n = read (args !! 0); m = read (args !! 1)
print (ant !! n !! m)
리스트 모나드의 함수((->)r) 모나드를 이용합니다.
$ time ./ant 99999 99999
3
real 0m0.529s
user 0m0.458s
sys 0m0.061s
# Look-and-say sequence
def main(x):
l=[['1',x[i]] for i in range(len(x))]
l2=[l[0]]
for i in range(1,len(x)):
if l[i][1]==l2[-1][1]:
l2[-1][0]=str(int(l2[-1][0])+1)
else:
l2.append(l[i])
s=' '
for i in range(len(l2)):
for j in range(len(l2[i])):
s+=l2[i][j]
return s[1:]
l=['1']
for i in range(999):
x=l[-1]
if len(x)>1000:
x=x[:1000]
l.append(main(x))
print('100번째 수열의 100번째 숫자는 {0}'.format(l[99][99]))
print('1000번째 수열의 1000번째 숫자는 {0}'.format(l[999][999]))
100번째까지 가는데도 시간이 아직 많이 걸립니다. 실력이 늘어서 더 좋은 알고리즘을 찾게 되면 다시 보강해서 올리도록 하겠습니다.
def say(integer):
s=str(integer)+' '
count=1
result=''
for i in range(len(s)):
if i>=len(s)-1:
break
if s[i]==s[i+1]:
count+=1
i+=2
else:
result=result+str(s[i])+str(count)
i+=1
count=1
return result
x=1
for k in range(10):
print(x)
x=say(x)
st = "1"
for i in range(100) :
print st
stnew = ""
chbfr = st[0]
num = 0
for j in range( len(st) > 100 and 100 or len(st) ) :
if chbfr == st[j] :
num += 1
else :
stnew = stnew + chbfr + chr( num + 48 )
num = 1
chbfr = st[j]
st = stnew + chbfr + chr( num + 48 )
print st[99]
허접한 풀이 ...
struct Lookandsay
{
int length;
int* arry;
};
#include<stdio.h>
#include<stdlib.h>
Lookandsay LookandsaySEQ(int* darry, int length);
void main(void) {
int length = 1;
int *darry = (int*)malloc(sizeof(int)*length);
darry[0] = 1;
Lookandsay las;
for(int i= 0 ; i < 1000; i++) {
las = LookandsaySEQ(darry, length);
if(i == 999) {
//for(int i = 0 ; i < 1; i++) {
printf("%d", las.arry[i]);
}
darry = (int*)malloc(sizeof(int)*las.length);
length = las.length;
darry = las.arry;
}
}
Lookandsay LookandsaySEQ(int* darry, int length) {
int *returnarr = (int*)malloc(sizeof(int)*(length*3));
if(length * 3 > 5000)
length = 5000;
int count = 1;
int j = 0;
Lookandsay las;
for(int i = 0 ; i < length ; i++) {
if(darry[i] == darry[i+1] && (i+1<length)) {
count++;
}
else {
returnarr[j] = count;
returnarr[j+1] = darry[i];
j= j+2;
count = 1;
}
}
las.length = j;
las.arry = returnarr;
return las;
}
1000000은 너무 느리게 실행되니 실패했다고 봐야 겠네요. ㅠㅠ 도전과제3은 C#으로 다시시도해야 겠어요
#include <stdio.h>
#include <stdlib.h>
void ant(char* in, char* out, int n){
char* pa = in;
char* pb = out;
char* bm = in;
int cnt = 0;
int i = 0;
while(*pa != 0){
if(*pa == *bm){
cnt++;
pa++;
}else{
*pb++ = cnt;
*pb++ = *bm;
cnt = 0;
bm = pa;
i++;i++;
if(i > (n + 1)){
break;
}
}
}
*pb++ = cnt;
*pb++ = *bm;
*pb = 0;
}
void say(int n){
char* a = malloc(2000000 * sizeof(char));
char* b = malloc(2000000 * sizeof(char));
a[0] = 1; a[1] = 0;
b[0] = 0;
char* pa = a;
char* pb = b;
char* pc;
for(int i = 0; i < n; i++){
ant(pa, pb, i);
pc = pa;
pa = pb;
pb = pc;
}
printf("%d\n", pb[n-1]);
free(a);
free(b);
}
int main(){
say(100);
say(1000);
say(1000000);
}
Java
public class AntNumberArray {
private static String toAntString(String s, int cnt, int n) {
String result = "";
char currentChar = ' ';
int currentLength = 0;
for (int i = 0; i < s.length() && result.length() <= cnt*3; i++) {
if (s.charAt(i) == currentChar) {
currentLength++;
} else {
if (currentLength != 0)
result += Integer.toString(currentLength) + Character.toString(currentChar);
currentChar = s.charAt(i);
currentLength = 1;
}
if (cnt < n - 48 && result.length() >= 3)
break;
}
result += Integer.toString(currentLength) + Character.toString(currentChar);
if (cnt < n - 48 && result.length() >= 3)
result = result.substring(0, 3);
return result;
}
public static String toAntStringNTimes(String str, int n) {
String s = str;
for (int i = 1; i < n; i++) {
s = toAntString(s, i, n);
if (n >= 1000000 && i > 1000000 - 50) System.out.println(i + ":" + s.length());
}
return s;
}
public static void main(String[] args) {
int n = 100;
System.out.println(n+"th:"+(AntNumberArray.toAntStringNTimes("1", n)).charAt(n-1));
n = 1000;
System.out.println(n+"th:"+(AntNumberArray.toAntStringNTimes("1", n)).charAt(n-1));
n = 1000000;
long startingTime = System.currentTimeMillis();
System.out.println(n+"th:"+(AntNumberArray.toAntStringNTimes("1", n)).charAt(n-1));
System.out.println("Time elapsed in seconds: " + (System.currentTimeMillis()-startingTime)/1000.0);
}
}
위에 분들에게 힌트를 얻어서 했습니다. 개미 수열은 그 길이가 급격히 증가 하네요. 모든 길이를 계산이 하니 답도 없어서 필요한 인덱스*3으로 잡아서 계산했습니다.
백만은 타임이 오버 되네요. 1천은 0.5초 정도 걸린거 같은데요.
/**
* Created by moonti on 2016. 10. 16..
*/
public class LookAndSaySequence {
private static final int SIZE = 1000005;
static String[] sequence= new String[SIZE];
static int n = 1000000;
public static void main(String[] args) {
sequence[0] = "1";
for (int i = 1; i<n; i++) {
sequence[i] = next(sequence[i-1]);
}
System.out.print(sequence[n-1].charAt(n-1));
}
public static String next(String string) {
int count = 1;
char pre = string.charAt(0);
char current = 'n';
StringBuffer result = new StringBuffer();
for(int i=1; i<string.length(); i++) {
current = string.charAt(i);
if (current == pre) {
count++;
} else {
result.append(count);
result.append(pre);
count = 1;
pre = current;
}
}
result.append(count);
result.append(pre);
if (result.length() > n*3) {
return result.substring(0, n*3);
} else {
return result.toString();
}
}
}
C:
#include <stdlib.h>
#include <stdio.h>
#define crBegin switch(s->ptr) { case 0:
#define crYield(x) do { s->ptr=__LINE__; return x; \
case __LINE__:; } while (0)
#define crEnd } return 0;
typedef struct proc proc;
struct proc {
int (*proc)(proc*); // 코루틴 함수 포인터
char ptr; // 재진입 위치
char next; // read 로 읽은 값
char prev; // 이미 읽은 값 (갯수를 세는 값)
char count; // 반복된 글자 갯수
};
int init(proc *s) {
crBegin;
crYield(1);
crEnd;
}
int next(proc *s) {
crBegin;
crYield(-1);
s->prev = s->next;
s->count = 1;
while(1) {
crYield(-1);
if (s->next == 0) {
break;
} else if (s->prev == s->next) {
s->count++;
} else {
crYield(s->count);
crYield(s->prev);
s->prev = s->next;
s->count = 1;
}
}
crYield(s->count);
crYield(s->prev);
crEnd;
}
int main(int argc, char** argv) {
int n = argc >= 2 ? atoi(argv[1]) : 10;
int m = argc >= 3 ? atoi(argv[2]) : 10;
// 코루틴 준비
proc* procs = (proc*)calloc(n + 1, sizeof(proc));
procs[0].proc = &init;
for (int i = 1; i < n + 1; i++) {
procs[i].proc = &next;
}
// 디스패치 루프
int cur = n;
while (cur < n + 1) {
int result = procs[cur].proc(&procs[cur]);
if (result == -1) {
cur--;
} else if (cur < n) {
cur++;
procs[cur].next = result;
} else if (result != 0) {
if (m-- == 0) {
printf("%d\n", result);
break;
}
} else {
printf("n/a\n");
break;
}
}
free(procs);
return 0;
}
n번째 줄 m번째 숫자를 출력합니다. 각 줄을 처리할 수 있게 코루틴을 n개 생성하고, n번째 코루틴의 출력 중 m번째 값을 프린트하고 종료합니다.
$ time ./ant 99999 99999
3
real 0m0.031s
user 0m0.023s
sys 0m0.003s
public void FindLookAndSaySequence(int input, string num)
{
for (int i = 0; i < input; i++)
{
num = FindLookAndSaySequenceLoop(num);
Console.WriteLine(num);
}
num = "1";
}
public string FindLookAndSaySequenceLoop(string input)
{
var count = 0;
var curr = default(char);
var output = new StringBuilder();
foreach (var c in input)
{
if (c != curr)
{
if (curr == default(char))
{
count = 1;
curr = c;
output.Append(curr);
}
else
{
output.Append(count);
count = 1;
curr = c;
output.Append(curr);
}
}
else count++;
}
output.Append(count);
return output.ToString();
}
MATLAB 입니다.
급격히 늘어나는 걸 감안해서, 마지막 20번을 제외하고는 앞부분만 읽어서 저장하는 형태로 했습니다. 이 부분을 좀더 꼼꼼하게 볼 필요는 있겠네요.
if n>=target_n_th_sequence-20 iter_len=min([length(str_n), target_n_th_number]); else iter_len=min([length(str_n), target_n_th_number/10]); end
100번째 수열의 100번째 숫자 1 (0.25초) 1000번째 수열의 1000번째 숫자 3 (7초) 백만번... 하세월이네요 ㅜㅠ
clear all
close all
tic
clc
% target_n_th_sequence=1000;
% target_n_th_number=1000;
target_n_th_sequence=100;
target_n_th_number=100;
%result=zeros(target_n_th_sequence,1,'string'); % string 형태로 저장할 듯
result{1}='1';
for n=2:target_n_th_sequence
if mod(n,target_n_th_sequence/10)==0
disp([sprintf('%d/%d',n,target_n_th_sequence) ' ' datestr(now,16)]);
end
% 이전 string을 읽기
str_n=result{n-1};
% 숫자의 빈도를 읽기
type_cnt=1;
freq_arr=cell(1,length(str_n)); % 등장한 숫자, 누적회수를 저장. 같은 종류만 된다...
freq_arr{type_cnt}=[1 str2num(str_n(1))]; % 첫번째 숫자가 등장했고, 한번 나왔다
if n>=target_n_th_sequence-20
iter_len=min([length(str_n), target_n_th_number]);
else
iter_len=min([length(str_n), target_n_th_number/10]);
end
for p=2:iter_len
if str2num(str_n(p))==freq_arr{type_cnt}(2) % 원래 있던 수인 경우 -> 빈도를 추가
freq_arr{type_cnt}(1)=freq_arr{type_cnt}(1)+1;
else % 새로운 수 -> 새로
type_cnt=type_cnt+1;
freq_arr{type_cnt}=[1 str2num(str_n(p))];
end
end
% 숫자형태로 변환
result_str=[num2str(freq_arr{1}(1)) num2str(freq_arr{1}(2))];
for p=2:type_cnt
result_str=[result_str [num2str(freq_arr{p}(1)) num2str(freq_arr{p}(2))];];
end
result{n}=result_str;
end
%%
disp([' ' ...
num2str(target_n_th_sequence) '번째 수열의 ' ...
num2str(target_n_th_number) '번째 숫자는 ' ...
num2str(result{target_n_th_sequence}(target_n_th_number)) ' 입니다']);
toc
#include<stdio.h>
#include<string.h>
void ant(char *ant);
int main(void) {
char arr[100000] = "1";
printf("%s\n", arr);
for (int i = 0; i < 20; i++) {
ant(arr);
printf("%s\n", arr);
}
}
void ant(char*ant)
{
char ant_back[100000]; //다음 수열을 넣을 배열
strcpy(ant_back, ""); //strlen을 쓰기위해 '\0'삽입
int count = 1;
int i;
int len = strlen(ant);
int backlen; //새로 만들 배열의 길이
for (i = 0; i < len; i++) {
if (i == len - 1) { //끝에 왔을 경우
backlen = strlen(ant_back);
ant_back[backlen] = count + '0';
ant_back[backlen + 1] = ant[i];
ant_back[backlen + 2] = '\0';
}
else if (ant[i] == ant[i + 1]) //똑같은 숫자가 나왔을 때
count++;
else if (ant[i] != ant[i + 1]) { //다른 숫자가 나왔을 때 (분기점)
backlen = strlen(ant_back);
ant_back[backlen] = count + '0';
ant_back[backlen + 1] = ant[i];
ant_back[backlen + 2] = '\0';
count = 1; //초기화
}
}
strcpy(ant, ant_back);
return;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define 번째수 1000 // 1000번째 값 구할경우. 100번째면 100으로 100만번째면 1000000으로 변경
#define 크기 1100 // 수열 기록될 공간입니다. 혹시 몰라 위에 번째수보다 약간 크게 주겠습니다.
int main(){
int iCount = 1, iPart;
char arrNum[10] = { 0 };
char *strResult = calloc(크기, sizeof(char));
//일반 배열로 선언하니까 어느이상 커지니까 안돼서 메모리할당 해줬습니다.
char *strTemp = malloc(sizeof(char) * 크기);
char *strTemp2 = malloc(sizeof(char) * 크기);
strResult[0] = '1'; //수열 첫번째 값
while (1) {
strcpy(strTemp, strResult); //임시 배열에 저장
memset(strResult, '\0', 크기);
while ((strlen(strTemp) >= 1)&&(strlen(strResult)<=(iCount+5))) {
// n번째수열의 n번째만 알면 되므로 넉넉하게 n+5번째까지만 계산
iPart = strTemp[0]-48; //문자형중 숫자부분의 아스키코드값 '0'이 48 '1'이 49인걸 이용해서 정수로 변환
arrNum[iPart]++; //각 숫자 갯수 한개씩 카운트
memmove(strTemp, strTemp + 1, strlen(strTemp)); // 맨앞숫자 카운트 했으므로 한칸씩 앞으로 땡기는 작업
if ((strTemp[0]-48)== iPart) {
continue; // 카운트한 숫자와 뒤에 숫자가 같을경우 계속 카운트
}
else { //같지 않을경우 strResult에 기록
strcpy(strTemp2, strResult);
sprintf(strResult, "%s%d", strTemp2, arrNum[iPart] * 10 + iPart); //새로 기록할부분 뒤에 붙이기
memset(arrNum, 0, 10); // 새로 카운트하기 위해 0으로 초기화
}
}
iCount++;
if (iCount == 번째수) // 해당 번째가 됐으면 벗어나기
break;
}
printf("%c", strResult[번째수-1]); //n번째수열의 n번째수 출력
free(strResult);
free(strTemp);
free(strTemp2); //메모리 할당 해제
return 0;
}
1000번째 까지는 금방 나오는데 그이상 가니까 컴퓨터가 구려서 그런지 한참 걸리네요. 10,000번째꺼까지는 잠시 딴거하다 오니 나오는데 100만번째는 포기했습니다. ㅋㅋ;;
다른 분들 힌트 참고했습니다.
수열 길이가 줄어들지 않는다고 가정하면(증명은 못 하겠습니다만) N*3이 아니라 N자리까지만 계산해도 됩니다.
수행 시간은 1000에서 3초 정도.
싸이클이 있지 않을까 해서 찾아보니 수학적으로 없다 합니다,
출력해보면 100일 때와 1000일 때 수열 앞부분이 같아 보이는데... 어떻게 이용할지 잘 모르겠네요.
def look_n_say(src, limit):
dst = [0, 0]
while src and len(dst) < limit + 2:
n = src.pop(0)
if n == dst[-1]: dst[-2] += 1
else: dst += [1, n]
return dst[2:]
def do(n):
lst = [1]
for i in range(1, n):
lst = look_n_say(lst, n)
return lst[n-1]
# python 3.6
def las(string, limit):
"""string: 입력 수열, limit: 수열의 문자열 길이 제한"""
seq = string
while True:
rst = seq[0]
for i in range(1, len(seq)):
if seq[i] != rst[-1]:
rst += ","
rst += seq[i]
seq = "".join([str(len(s)) + s[0] for s in rst.split(",")])
if len(seq) > limit:
seq = seq[:limit]
yield seq
# 문제, 도전 1
my_seq = las("1", 1000) # sequence(1) (문자수 제한 = 1000)
for i in range(2, 1001):
result = next(my_seq) # sequence(2), ... seq(1000)
if i == 100:
print(i, result[i - 1])
if i == 1000:
print(i, result[i - 1])
# 도전 2
"""수열의 길이가 기하급수적으로 증가하므로
계산 시간 단축을 위해 999950번째 까지는 문자수를 10개로 제한,
이후 50개의 수열만 100만 자리까지로 계산"""
my_seq = las(result, 10) # sequence(1000)에서 문자수 제한(= 10) 재 설정
for i in range(1001, 999951):
result = next(my_seq) # sequence(1001), ... seq(999950)
my_seq = las(result, 10**6)
for i in range(999951, 10 ** 6 + 1): # sequence(999951), ..., seq(10**6)
result = next(my_seq)
if i == 10 ** 6:
print(i, result[i - 1])
# ans:
# 100 1
# 1000 3
# 1000000 1
#include<iostream>
#include"stdafx.h"
void Look_And_Say_Sequence(string &str, string &temp, string::size_type i,int seq_num)
{
if (str.size() == 1)
{
str = "11";
return;
}
int num_count = 1;
while (1)
{
if (i == str.size()||i==seq_num)
{
str = temp;
temp.clear();
break;
}
if (str[i] == str[i + 1])
{
i++;
num_count++;
}
else
{
temp += to_string(num_count);
temp += str[i];
i++;
num_count = 1;
}
}
}
int main()
{
string str = "1", temp;
str.reserve(1000000);
clock_t before = clock();
for (int i = 1; i < 1000; i++)
{
Look_And_Say_Sequence(str, temp, 0,i*3);
}
cout << str[999] << endl;
cout << "수행시간:" << (double)(clock() - before) / CLOCKS_PER_SEC << endl;
}
파이썬 3
def next(s):
result = []
char = ""
sub_result = ""
for i in range(len(s)):
if i == 0:
sub_result = s[i]
elif s[i] == char:
sub_result += s[i]
else:
result.append(sub_result)
sub_result = s[i]
char = s[i]
result.append(sub_result)
result_str = ""
for lst in result:
result_str += (str(len(lst)) + lst[0])
return result_str
def nth_number(n):
nth = ""
for i in range(n):
if i == 0:
nth = "1"
else:
nth = next(nth)
return nth, nth[n-1]
print(nth_number(10))
8을 넣었을 때의 결과
('1113213211', '2')
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace 개미수열
{
class Program
{
static void Main(string[] args)
{
string sequence = "1";
int n = 1;
List<string> antList = new List<string>();
antList.Add(sequence);
while (n <= 99)
{
char token = sequence[0];
int count = 0;
string tempSequence = "";
for (int i = 0; i < sequence.Length; i++)
{
if (token == sequence[i])
count++;
else
{
tempSequence += "" + token + count;
count = 0;
token = sequence[i];
count++;
}
if (i + 1 == sequence.Length)
tempSequence += "" + token + count;
if (tempSequence.Length > 100)
{
break;
}
}
sequence = tempSequence;
antList.Add(sequence);
if (n == 99)
Console.WriteLine("100번째 수열의 100번째 수 : " + antList[99].Substring(99, 1));
n++;
}
}
}
}
import re
def ant(idx):
n = '1'
for _ in range(idx-1):
n = re.sub('(\d)\\1*', lambda x: str(len(x.group()))+x.group(1), n)[:idx+2]
return n[idx-1]
print(ant(1000))
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void part(string s,int&);
int main(void)
{
int pre;
cin >> pre;
int cnt;
string s("1");
part("1", pre);
}
void part(string s,int &p) {
static int num = 0;
string a;
if (num == p)return;
int cnt = 1;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == s[i + 1])cnt++;
else
{
a.push_back(cnt + 48);
a.push_back(s[i]);
cnt = 1;
}
}
for (string::iterator itr = a.begin(); itr != a.end(); itr++)
{
cout << *itr;
}
num++;
cout << endl;
part(a, p);
}
import re
t ='(1+|2+|3+|4+|5+|6+|7+|8+|9+)'
def say(k):
s='1'
for i in range(k-1):
s = re.sub(t, lambda m : str(len(m.group()))+m.group()[0], s)
if len(s) > k + 100:
s = s[0:k+100]
return s
print(say(1000)[1000-1])
import re
re_com = re.compile("1+|2+|3+|4+|5+|6+|7+|8+|9+|0+")
def ant(ini, obj, state) :
k = re_com.findall(ini[:2*obj])
if obj != state :
return ant("".join(map(lambda x : str(len(x))+str(x[0]), k))[:2*obj], obj, state+1)
elif obj == state :
return "".join(map(lambda x : str(len(x))+str(x[0]), k))[state-1]
print(ant('1', 100,2))
print(ant('1', 1000,2))
위의 답에서 힌트를 얻어 정규표현식과 재귀함수를 활용하였습니다. 100만자리까지 계산하기에는 아직 실력이 많이 부족하네요.
결과
1
3
public static String lookAndSaySequence(String number, int n) {
String result = "";
String temp = "";
String[] num = number.split("");
for (int i = 1; i < n; i++) {
int cnt = 1;
temp = "";
if (num.length == 1) {
temp = String.valueOf(cnt).concat(num[num.length - 1]);
num = temp.split("");
temp = "";
i++;
}
for (int j = 1; j < num.length && temp.length() <= i * 3; j++) {
if (num[j].equals(num[j - 1])) {
cnt++;
} else {
temp += String.valueOf(cnt).concat(num[j - 1]);
cnt = 1;
}
if (j == num.length - 1) {
temp += String.valueOf(cnt).concat(num[j]);
}
}
num = temp.split("");
}
result = num[n - 1];
return result;
}
def sequence(N, sq):
n = 1
overN = 0
while n < N:
cnt = 1
sqN = ''
for i, s in enumerate(sq):
if i+1 < len(sq) and s == sq[i+1]:
cnt += 1
elif i+1 < len(sq) and s != sq[i+1]:
sqN += str(cnt) + s
cnt = 1
if len(sqN) > N and (n+1) % 3 == N % 3:
overN += 1
break
sqN += str(cnt) + sq[-1]
sq = sqN
n += 1
if overN > 4:
break
return sq
nth = 10
print(sequence(nth, '1'))
print(sequence(nth, '1')[nth-1])
nth = 100
print(sequence(nth, '1')[nth-1])
nth = 1000
print(sequence(nth, '1')[nth-1])
nth = 1000000
print(sequence(nth, '1')[nth-1])