개미수열 알고리즘

안녕하세요? QRD입니다.

혹시 베르나르 베르베르의 소설 <개미>에서 나오는 개미수열 이라고 아시나요?
자세한 사항은 네이버 캐스트에서 확인해 보실 수 있습니다.
저는 어떠한 수열인지에 대해서만 확인해 보도록 하겠습니다.

1

1, 1

1, 2

1, 1, 2, 1

1, 2, 2, 1, 1, 1

1, 1, 2, 2 ,1, 3

…

이러한 수열인데요, 설명 드리겠습니다.

1) 첫 숫자는 1입니다.
2) 두번째 수열은 이전의 수열에서 숫자의 개수를 의미합니다. <1, 1 이라는 것은 1의 숫자는 한개> 의미입니다.
3) 세번째 수열은 두번째 수열의 숫자의 개수를 의미합니다. <1, 2 라는 것은 1의 숫자는 두개> 의미입니다.
4) 네번재 수열은 세번째 수열의 숫자의 개수를 의미합니다. <1, 1, 2, 1 라는 것은 1의 숫자는 한개, 2의 숫자는 1개> 의미입니다.
5) 다섯번째 수열은 네번째 수열의 숫자의 개수를 의미합니다.
<1, 2, 2, 1, 1, 1 라는 것은 1의 숫자는 2개, 2의 숫자는 1개, 1의 숫자는 1개> 의미입니다.

위와 같이 반복적으로 수열을 만들어 가는 건데요. 가장 중요한 점은 연속된 숫자에 대한 개수라는 것입니다.
다섯번째 수열을 보시면 이해하실 수 있을겁니다.
그렇다면 이 수열을 자바 알고리즘으로 코딩해 보겠습니다.
항상 말씀드렸다시피 다양한 방법이 존재하고 저의 코드가 정답이 아니며, 더 좋은 알고리즘이 있을 때 공유해주시면 정말 감사하겠습니다.
(같이 배워요 ㅎㅎ)

	public static void main(String args[]) {
		antSequence();
	}

	public static boolean antSequence(){
 		ArrayList <String> resultArray = new ArrayList ();
		ArrayList <String> beforeResultArray = new ArrayList ();
		ArrayList <String> tempArray = new ArrayList ();
		resultArray.add("1"); // 초기값
		int k = 0;
		while(k < 10){ //수열의 행 개수
			System.out.println(resultArray);
			
			int count = 0;
			int tempCount = 0;
			beforeResultArray.clear(); // 이전의 결과를 담아 놓는 리스트
			tempArray.clear(); // 표현해야 할 숫자를 담아놓는 리스트 (중복 제거용)
			
			for (int i = 0; i < resultArray.size(); i++) { //결과를 담은 리스트를 beforeResultArray 로 복사
				beforeResultArray.add(resultArray.get(i));
			}
			
			tempArray = removeDuplication(beforeResultArray); // 중복제거 후 숫자만 리스트에 담아 놓음.

			resultArray.clear();//현재 열의 수열을 담기 위해 내용 초기화
						
			for (int f = 0; f < tempArray.size(); f++) {				
				count = 0;
				String temp = tempArray.get(f); 
				resultArray.add(tempArray.get(f)); // 숫자의 중복을 제거한 후 하나씩 꺼냄
				for (int d = tempCount; d < beforeResultArray.size(); d++) {// 꺼낸 숫자의 개수를 검사함
					if(temp.equals(beforeResultArray.get(d))){
						count ++ ;
					}else{
						tempCount = d; // 같지 않다면 다른 숫자인 것이므로 tempCount에 이전까지 검색한 위치를 담아 놓음.
						break; // for문을 빠져나온다.
					}
				}
				resultArray.add(String.valueOf(count)); // 카운트한 숫자를 리스트에 넣는다.
			}
			k++;
		}
		return false;
	}
	
	/**
	 * 연속된 숫자의 중복을 제거 해주는 함수 
	 * 예를 들어 1,1,2,1 일 때 결과 값은 1,2,1
	 * @param source
	 * @return
	 */
	public static ArrayList <String> removeDuplication(ArrayList source)
	{
		ArrayList <String> tempArray = new ArrayList <String>(); // 바로 앞의 숫자와 현재 숫자를 비교, 다를 때 리스트에 삽입
		for(int j = 0; j < source.size(); j++){
			if(j == 0){
				tempArray.add(source.get(j));
			}else{
				if(!source.get(j-1).equals(source.get(j))){
					tempArray.add(source.get(j));
				}
			}
		}
		return tempArray;
	}
	

저는 이렇게 코딩해보았습니다.

저는 맨 처음 표현해야 할 숫자에 주목을 하였습니다.
removeDuplication() 함수에서 그 역할을 하게 될 건데요, 함수를 보시면 첫번째 숫자는 tempArray에 넣습니다.
두번째 숫자는 첫번째 숫자와 비교 후 다르면 tempArray에 넣습니다.
이런 식으로 하다보면 결국 n번째 숫자가 n-1번째 숫자와 다를 때 tempArray에 넣어줌으로써 연속된 숫자들의 중복을 없앤 숫자만 남게 됩니다.(주석 참조)

그 후 tempArray 리스트에서 숫자를 꺼내 결과를 만드는 resultArray 에 넣어준 후,
이전 수열에서 해당하는 숫자의 카운트를 resultArray 리스트에 넣어줌으로써 개미수열을 완성할 수 있었습니다.

주석을 참조하여 이해하시면 간단히 되실 거 같습니다.

감사합니다!!!

감사합니다. QRD였습니다. 꾸벅(_ _)