알고리즘 코딩 이벤트 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");
}
}
덧글