[코딩테스트 / Java] 개미수열

모회사 코딩테스트 중 개미수열에 대해 알게되어 흥미가 생겨 정리해봤습니다

 

개미수열이란?

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

1

11

12

1121

122111

112213

12221131

 

[법칙]

1.  1 => "1이 한 개" / 따라서 다음 열 => "11"
2. 11 => "1이 두 개" / 따라서 다음 열 => "12"
3. 12 => "1이 한 개, 2가 한 개 " / 따라서 다음 열 => "1121"
4. 1121 => "1이 두 개, 2가 한 개, 1이 한 개" / 따라서 다음 열 => "122111"
5. 122111 => "1이 한 개, 2가 두 개, 1이 세 개" / 따라서 다음 열 => "112213"
6. 반복

정리하자면

• 한 열은 결과가 나오는 동시에 다음에 나올 열의 규칙이 된다.
• "숫자+갯수"의 반복이다.
• 같은 숫자의 연속이면 갯수를 세고, 다른 숫자가 시작되면 새로운 갯수를 센다.

 

코드

public class AntSequence {
	
	public static void main(String[] args) {
		//인자로 반복갯수를 넣는다
        antsequence(10);
	}
	
	public static void antsequence(int times) {
		String result = "1"; //시작은 1이다
		for(int i = 0; i<times; i++) {
			if(i != 0) {
				String[] input = result.split("");
				result = "1";
				String target = ""; //반복 갯수 => 추후에 length를 활용
				for(int j = 0; j < input.length; j++) {
					if(j == 0) {
						target = input[j];
					}
					else if(target.split("")[0].equals(input[j])) {
						//똑같은 문자 target에 append
						target += input[j];
					} else {
						//다른 문자 result target 수를 append, 첫 문자는 target에 append
						result += target.length() + input[j];
						target = input[j];
					}
					
					if(j == (input.length -1)) {
						result += target.length();
					}
				}
			}
			//출력
			System.out.println(result);
		}
	}
}

10번 반복시 아래와 같은 결과가 나온다.