PostAddsense


DivideByZero Topcoder



import java.util.Arrays;
import java.util.HashSet;

public class DivideByZero
{
    public int CountNumbers(int[] numbers) {
        HashSet<Integer> paper = new HashSet<Integer>();
        for (int i : numbers) paper.add(i);

        int old = 0;
        while (paper.size() > old) {
            old = paper.size();
            HashSet<Integer> clone = (HashSet)paper.clone();
            for (int a : clone)
                for (int b : clone)
                    if (a>b) paper.add(a/b);
        }

        return paper.size();
    }
}


Explanation

※ Set을 그대로 사용시 수정된 Set으로 for문을 돌리게 되고 java.util.ConcurrentModificationException 오류가 발생한다. 따라서 Set을 얕게 복사하는 clone을 사용한다.

중복값이 없도록 Set: paper를 만들어 numbers 배열의 모든 값을 넣는다. 이전 paper가 현재 paper보다 크기가 작다면 현재 paper에 새로운 값이 추가됐다는 뜻이므로 while문은 계속 반복된다. 이전 paper가 현재 paper와 크기가 같다면 새로운 값이 추가되지 않았단 뜻이므로 while문은 종료되고 현재 paper의 크기를 반환한다.

List로도 구현가능하다. 대신에 a/b값이 있는지 없는지를 확인하기 위해,  if (a>b && !paper.contains(a/b)) 를 추가해야 한다.


References