관리 메뉴

취미개발 블로그와 마음수양

개미수열 나도 풀어보자. ㅎㅎㅎ 본문

Language/java소스

개미수열 나도 풀어보자. ㅎㅎㅎ

아라한사 2014. 10. 30. 22:23

지니어스에 나온 프로그래머 이두희님께서 구글과 함께, 대학생들에게 코딩교육을 해주시는 프로그램을 운영 중이십니다

거기서 가르칠사람을 뽑는 문제로 파이썬으로 개미수열을 구현(10 분 안에... 헉.. ) 하는 것이 문제라고 하는데요.


저도 나름, 프로그래머를 생각하는 사람인지라 개미수열을  풀어보았습니다. 

일단 개미수열을 잘 모르는 사람을 위해 설명을 적어보겠습니다.


네이버 링크 : http://navercast.naver.com/contents.nhn?rid=22&contents_id=2322


먼저 알고리즘을 풀어내는 방법은 다음과 같습니다. 

1. 문제를 이해하고

2. 어떻게 풀지 계획하고

3. 계획을 수행하여 문제를 해결하고

4. 어떻게 풀었는지 돌아보고, 개선할 방법을 생각해본다.


여기서 문제를 이해해보자면, 저는 처음에 이것을 봤을 때 정말 이해를 못 했습니다. (ㅠ) 

설명을 보고 알았음 ㅠㅠ





먼저 1로 시작을 하는데

1이 1개가 있으므로 11 이고

그 다음에는 1이 두개가 있으므로 1 2 입니다.


다음에는 다시 1 이 한개가 있으므로 1 1 에 2가 1개가 있으므로 2 1 인 것입니다. 그림으로 설명하자면 다음과 같습니다.



아직 지능이 딸려서, 바로 실시간으로 프로그래밍은 안되고.. 우선 종이에 풀어보는 것을 매우 즐겨하기 때문에 종이로 적어보았습니다. (1. 문제 이해) 

그후 프로그래밍적으로 어떻게 할지 생각해보았습니다. 가장 작은 기능부터 구현하는 것이 저의 스타일입니다.


1을 넣었을 때 1 1을 구현하였습니다.

아참 미리 생각을 한게.. 배열을 쓰자니 숫자가 커지면 한계가 있을 것같고...

String은 자주 바뀌는 값에서는 쓰레기객체 때문에 메모리 사용이 비효율적일수도 있고..(JVM 1.5 버젼부터는 알아서 잘 계산해주는 경우도 들었는데 잘 모르겠슴..)

StringBuffer와 Stringbuilder 가 생각나는데

StringBuffer는 쓰레드안전. Stringbuilder는 단일쓰레드라고 일단 책을 읽은 게 생각나서 Stringbuilder로 구현을 해보려고 합니다.


일단 1 일 때 1 1을 뽑는 것부터 구현을 생각하면


윗줄이 1이고 아랫줄이 1 1 이 나와야 합니다. 윗줄 Stringbuilder에는 1을 넣어주고 아랫줄에 답을 넣어주려고 합니다. 

일단 변수 지정 !  



카운트 라인은 1번째 라인,2번째 라인을 계속 만들것이고, 나머지는 뭐.. 뻔한 변수명이니 생략 ㅎ

i는 현재 라인을 검사할 것이고.. 해서 


일단 첫번째 문자를 받아옵니다. 1을 받아오겠죠.. 그리고 i 를 0으로 해서 문자열 검사를 돌립니다.




for , if, for 이런것을 최대한 간단히 돌리자는 생각입니다만-_-

그냥 생각나는 대로 코딩하려니 중간에 더러운 if 가 한개 더 끼어버렸습니다. 

마지막 에 숫자가 딸랑 한개 남기고 끝나는 경우 추가 작업을 하나 더해줍니다. 

중복된 코드가 있지만, 그냥 내비둡니다.




그리고 마지막 넥스트라인을 현재줄로 끌어올려서 현재라인 출력!! 마무으리~,~;;


하지만 뭔가 에러가 나죠...

예..


1 을 처리하다가 숫자가 바뀌는 경우 다시 재귀함수를 돌아야하는지 돌지가 않았습니다. 그래서 마지막에 조금만 더넣어줍니다;; 바로 이 부분이죠 ㅎㅎ;; 



음...막상 돌리면 이렇게 뜨네요.. 일단은 되는 것같은데;;

28정도 가면 뭔가 글이 안뜨면서 50정도만 입력해도 스택오버플로우뜨네요;ㅁ;....


알고리즘 공부도 중요하지만, 익혀야할 프레임워크 공부 때문에 일단 이만...소스는 맨뒤에 통짜로 적습니다...그럼;;

일단 익숙한 자바로 했는데 10분을 넘겼군요.ㅠ..ㅠ...하 이걸 어떻게 10분안에 푼단말인가..천재들만 모인곳이란 말인가 ㄷㄷ;;


지금 공부하는 파이썬은 형변환에 좀 자유로운 편이니, 파이썬에 조금 더 익숙해지면 파이썬으로도 풀어봐야겠습니다.



package etc.algo;


import static org.junit.Assert.*;


import java.util.Scanner;


import org.junit.Test;


public class AntSequence {


int count = 0;

int position = 0;

int countLine = 0;

char temp;

int i;


StringBuilder currentLine = new StringBuilder("1");

StringBuilder nextLine = new StringBuilder();


@Test

public void ant() throws Exception {

System.out.print("몇번 돌리실 생각입니까? : ");

Scanner scanner = new Scanner(System.in);

int x = scanner.nextInt();

show();

for (int i = 0; i < x; i++) {

calculate();

}

scanner.close();

}


public void calculate() {

temp = currentLine.charAt(0);

i = 0;

checkLine();

currentLine.setLength(0);

currentLine.append(nextLine);

nextLine.setLength(0);

countLine++;

show();

}

public void checkLine() {

count = 0;

for (; i < currentLine.length(); i++) {

if (temp == currentLine.charAt(i)) {

count++;

if (i == currentLine.length() - 1) {

nextLine.append(temp);

nextLine.append(count + "");

}

} else {

nextLine.append(temp);

nextLine.append(count + "");

temp = currentLine.charAt(i);

checkLine();

}

}

}


void show() {

System.out.println(countLine + " : " + currentLine);

}



}