개미수열

읽고 말하기 수열은 다음과 같이 시작하는 수열이다. (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이다.

읽고말하기수열 Look-and-say sequence lazy run-length
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

11개의 풀이가 있습니다. 1 / 2 Page

개미수열의 임의의 항 내의 연속된 숫자는 [개수][숫자]의 조합으로 정리됩니다. 이렇게 정리되는 마디(?)들을 볼 때, 앞 마디의 [숫자]와 현 마디의 [개수]가 같거나, 현마디의 [숫자]와 뒷마디의 [개수]가 같은 식으로 같은 숫자는 최대 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"
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
# 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#으로 다시시도해야 겠어요

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

  • 한자리에서 시작해서 백만자리 넘어가기까지는 50회의 계산이 필요함.
  • 개미수열은 같은 수가 최대 세 번까지만 반복가능함.
  • 위의 두 전제를 바탕으로 백만 번에서 최종 48회 정도만 계산하면 백만자리 넘음.
  • 계산 과정에서는 N*3으로 넉넉하게 잡고 계산함.
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);
    }
}

결과

  • 100th:1
  • 1000th:3
  • 999951:3
  • 999952:6
  • 999953:6
  • 999954:10
  • ...
  • 999998:1321900
  • 999999:1724088
  • 1000000th:1
  • Time elapsed in seconds: 829.728
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

JAVA

위에 분들에게 힌트를 얻어서 했습니다. 개미 수열은 그 길이가 급격히 증가 하네요. 모든 길이를 계산이 하니 답도 없어서 필요한 인덱스*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();
        }
    }

}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

run-length x 2
lazy x 1
읽고말하기수열 x 1
Look-and-say sequence x 1
연관 문제

언어별 풀이 현황
전 체 x 11
haskell x 2
python x 3
기 타 x 1
java x 2
cpp x 3