2012/09/03 17:36

문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이

알고리즘 코딩 이벤트 1주차 2번째 문제


두 번째 문제를 풀어보았습니다.

n이 16 이하라는 조건이 있습니다. 16이면 이미 100억개 이상의 분할이 나오죠. 
현실적으로 모든 경우를 다 찍어보는 건 불가능할 것 같네요.
 몇 가지 경우가 있는지 가짓수 세는 문제 정도가 더 적절하지 않았을까 싶습니다.

처음에는 Set으로 결과 전체를 리턴하도록 했었는데 숫자가 커지면 불가능할 듯 해서 
Iterator만 리턴해서 하나씩 찍어낼 수 있도록 수정했습니다. 
n=12인 케이스의 경우 총 4213597가지 경우가 있는데 전부 출력시킬 때 제 노트북에서 254.86초 걸렸으니
n=16 케이스를 다 찍으려면 컴퓨터를 일주일 쯤 돌려야 할 것 같네요. 

내부적으로 분할 방법을 표현할 때에는 각 집합에 ID를 부여하고 각각의 숫자마다 이 ID를 할당시켜서 표현하도록 했습니다.


package insightbook.event.week1second;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class Division {

private int numberOfSet;
private int[] setIds;

public Division() {
numberOfSet = 1;
setIds = new int[] { 0 };
}

private Division(int numberOfSet, int[] setIds) {
this.numberOfSet = numberOfSet;
this.setIds = setIds;
}

private Division addElementAsSeparateSet() {
int length = setIds.length;
int[] setIds = Arrays.copyOf(this.setIds, length + 1);
setIds[length] = numberOfSet;

return new Division(numberOfSet + 1, setIds);
}

private Division addElementWithCurrentSet(int setId) {
int length = this.setIds.length;
int[] setIds = Arrays.copyOf(this.setIds, length + 1);
setIds[length] = setId;

return new Division(numberOfSet, setIds);

}

@Override
public String toString() {
return toIntSetCollection().toString();
}

Collection<Set<Integer>> toIntSetCollection() {
Map<Integer, Set<Integer>> map = new TreeMap<>();
for (int i = 0; i < numberOfSet; i++)
map.put(i, new TreeSet<Integer>());

for (int i = 0; i < setIds.length; i++) {
map.get(setIds[i]).add(i);
}

ArrayList<Set<Integer>> sets = new ArrayList<>();

for (Entry<Integer, Set<Integer>> e : map.entrySet()) {
sets.add(e.getValue());
}
return sets;
}

public static Iterator<Division> divisionIter(final int n) {

if (n == 1) {
return Arrays.asList(new Division()).iterator();
}

return new Iterator<Division>() {

Iterator<Division> innerIter = divisionIter(n - 1);
Division current = null;
int i = 0;
boolean startFlag = true;
boolean hasNext = innerIter.hasNext();

@Override
public boolean hasNext() {
return hasNext;
}

@Override
public Division next() {
if (current == null) {
if (innerIter.hasNext())
current = innerIter.next();
else
return null;
}

if (startFlag) {
startFlag = false;
return current.addElementAsSeparateSet();
}

Division next = current.addElementWithCurrentSet(i++);

if (i >= current.numberOfSet) {
if (!innerIter.hasNext())
hasNext = false;
else
current = innerIter.next();
startFlag = true;
i = 0;
}

return next;
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}

};

}

public static void main(String[] args) {
int n = 12;
Iterator<Division> iter = divisionIter(n);

long time0 = System.nanoTime();

while (iter.hasNext())
System.out.println(iter.next());

long time1 = System.nanoTime();
System.out.println("Total Time: "+(double)(time1-time0)/1000000000 +"sec");
}

}

덧글

  • 흑염패아르 2012/09/03 18:15 # 답글

    ................................외계어야 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
  • 성큼이 2012/09/04 10:38 #

    ㅋㅋ 프로그래밍에 관심없으면 몰라도 되는 이야기 ^^;
댓글 입력 영역