개미수열

베르나르 베르베르의 소설 "개미"에 나왔던 수열 문제 입니다.

1

11

12

1121

122111

112213

12221131

<- 다음에 나오는 수는 무엇일까요?

[법칙]

첫 시작은 1로 시작합니다.

1

--1이 1개 이므로 

11

--1이 2개 이므로

12

--1이 1개고 2가 1개 이므로

1121

 

위 법칙대로라면 12221131 다음에 나오는 수는 1123123111 입니다.

재미있는 사실은 시작 숫자가 1일 경우 1,2,3만 나온다는 건데요. 인터넷에 찾아보면 다양한 언어와 풀이법이 있네요. 아래 네이버에 개미수열에 대해 교수님이 자세히 정리한 글이 있네요.

개미수열이란

개미 수열

개미수열을 프로그래밍 하려면 여러가지 언어를 이용하는 다양한 방법이 존재합니다.

java로 잠깐 시간을 내서 생각나는대로 작성.

package com.tistory.kisspa;

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {

        ArrayList<String> arr = new ArrayList<String>();
        arr.add("1"); // 시작값
        for (int i = 0; i < 10; i++) { // 10개까지..
            print(arr);  // ArrayList를 예쁘게 출력
            arr = say(arr); // 계산하는 함수
        }
    }

    public static ArrayList<String> say(ArrayList<String> tmparr) {
        // 계산된 값을 넣을 컬렉션
        ArrayList<String> sayarr = new ArrayList<String>();
        String start = tmparr.get(0); // 첫번째 값을 가져온다.
        sayarr.add(start); // 계산된 값을 넣을 컬렉션에 넣는다.
        int cnt = 0;  // 동일한 숫자를 카운트 할 변수
        // 인자로 받은 컬렉션을 for문 돌리자.
        for (int i = 0; i < tmparr.size(); i++) {
            if( start.equals(tmparr.get(i)) ) {
                cnt++; // 숫자가 동일하다면 카운트 +1
            } else {
                sayarr.add(String.valueOf(cnt)); // 숫자가 다르다면 지금까지 카운트를 컬렉션에 추가
                sayarr.add(tmparr.get(i)); // 다음 계산할 숫자를 넣자
                start = tmparr.get(i); // 시작지점을 다음 계산할 숫자 위치로 변경
                i = i-1; // 시작지점부터 다시 for문 수행할 수 있게 -1
                cnt = 0; // 동일 숫자 카운트 초기화
            }
        }
        sayarr.add(String.valueOf(cnt)); // 마지막 카운트 추가
        return sayarr;
    }

    public static void print(ArrayList<String> arr) {
        for (int i = 0; i < arr.size(); i++) {
            if ((i+1) == arr.size()) {
                System.out.println(arr.get(i));
            } else {
                System.out.print(arr.get(i));
            }
        }

    }
}