Python Challenge # LV.10 (개미 수열)

출처) http://www.pythonchallenge.com/index.php

The Python Challenge

 

 

http://www.pythonchallenge.com/pc/return/bull.html

[그림1. LV.10 문제]

 

• 파이썬 챌린지 레벨10 문제!
• 소 이미지와 하단에 노란색으로 "len(a[30])=?"이라고 적혀있다.
• 소 이미지를 클릭해보면 다른 페이지로 넘어간다.

 

[그림2. sequence.txt]

 

• a가 있는 걸로 봐서 "len(a[30])=?" 문제에 대한 해답을 여기서 찾는 것 같다.
• 30번째일 때 길이를 묻는 것 같다.
• 1, 11, 21, 1211..... 숫자들의 조합을 보면 규칙이 있는 것 같은데 그냥 구글에 검색해보았다.

보고 말하기 수열(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

참고)위키백과

 

 

구현이 쉬울 줄 알았는데 코드가 너무 길어져서 풀이를 참고했다.

a = '1'
b = ''
for i in range(0, 30):
    j = 0
    k = 0
    while j < len(a):
        while k < len(a) and a[k] == a[j]: 
            k += 1
        b += str(k-j) + a[j]
        j = k
    print("output:",b)
    a = b
    b = ''
print(len(a))

[그림3. 구현 결과]

 

[그림4. 정규표현식 구현]

다른 풀이도 찾아보니 간단하게 정규표현식으로 구현하기도 했다.

 

 

 

• 답 : 5808
• http://www.pythonchallenge.com/pc/return/5808.html 로 가면 다음 레벨 문제가 나온다.