개미수열

지나가다 본 문제인데 호기심이 생겨 풀어보았다.

문제는 다음과 같다.

개미수열? http://navercast.naver.com/contents.nhn?rid=22&contents_id=2322

출처 : https://www.facebook.com/photo.php?fbid=718742614882121&set=gm.870169196356951&type=1

'읽고 말하기 수열' 이라고 부르는 것같은데 바로 위에 있는 수가 몇 개인지 쭈-욱 나열하는 것이다.

1

11 (1이 1개)

12 (1이 2개)

1121 (1이 1개 2가 1개)

...

C, Python, Java로 각각 풀어보았다.

1. C (재귀)

#include <stdio.h>
#include <string.h>

const int MAX_DEPTH = 10;

int getLength(char *pChar)
{
    char ch = *pChar;
    int count = 0;

    while(*pChar &amp;&amp; *pChar == ch) {
        count++; pChar++;
    }

    return count;
}

void solve(char *pChar, int depth)
{
    printf("%s\n", pChar);

    if (depth &gt;= MAX_DEPTH) return ;

    char output[64];
    memset(output, 0, sizeof(output));

    while(*pChar) {
        int len = getLength(pChar);
        sprintf(output, "%s%c%d", output, *pChar, len);
        pChar += len;
    }

    solve(output, depth+1);
}

int main()
{
    solve("1", 0);
    return 0;
}

2. Python (루프)

MAX_LOOP = 10

def get_length(num_str):
    first_char = num_str[0]
    for i in range(0, len(num_str)):
        if num_str[i] != first_char:
            return i
    return len(num_str)

def solve(num_str):

    new_str = ""
    start_pos = 0

    while start_pos < len(num_str):
        length = get_length(num_str[start_pos:])
        new_str += num_str[start_pos] + str(length)
        start_pos += length

    return new_str

if __name__ == '__main__':
    num_str = "1"
    for i in range(MAX_LOOP):
        print str(i) + ": " + num_str
        num_str = solve(num_str)

3. Java

public class MorrisGenerator {

    private final String PARTITION_MARK = " ";

    public void generate(int limit) {
        String str = "1";
        for(int i = 0; i < limit; i++) {
            System.out.println(str);
            str = makeMorrisNumber(makePartitionedStr(str).split(PARTITION_MARK));
        }
    }

    private String makeMorrisNumber(String[] strs) {
        String morris = "";

        for(String s : strs) {
            morris += (s.charAt(0) + String.valueOf(s.length()));
        }

        return morris;
    }

    private String makePartitionedStr(String str) {
        String newStr = "";
        char bChar = str.charAt(0);

        for(int i = 0; i < str.length(); i++) {
            char nChar = str.charAt(i);
            if (bChar != nChar) {
                newStr += PARTITION_MARK;
            }
            bChar = nChar;
            newStr += nChar;
        }

        return newStr;
    }

    public static void main(String[] args) {
        MorrisGenerator mg = new MorrisGenerator();
        mg.generate(10);
    }
}

그리고, 이런 풀이도 .. ^^;

http://stackoverflow.com/questions/553871/can-anyone-provide-a-more-pythonic-way-of-generating-the-morris-sequence

붙여놓으면 다음과 같다. 입력이 반복 수가 아닌 문자열 길이라는게 차이점

import itertools

def next_morris(number):
    return ''.join('%s%s' % (digit, len(list(group)))
        for digit, group in itertools.groupby(str(number)))

def morris_generator(maxlen, start=1):
    num = str(start)
    while len(num) < maxlen:
        yield int(num)
            num = next_morris(num)

for n in morris_generator(10):
    print n