Ugly Numbers/Damien Rice

첫 번째 방법 ¶

def ugly(pos):
    count = 0
    uglys = [2,3,5]
    minVal = 0
    while count != pos-1:
        minVal = min(uglys)
        if uglys.count(minVal*2)==0:
            uglys.append(minVal*2)
        if uglys.count(minVal*3)==0:
            uglys.append(minVal*3)
        if uglys.count(minVal*5)==0:
            uglys.append(minVal*5)

        uglys.remove(minVal)
        count += 1

    print minVal

if __name__=='__main__':
    ugly(1500)

- 위의 코드를 그대로 ruby문법에 맞게 옮긴 버전

def ugly(pos)
    count = 0
    uglys = [2,3,5]
    minVal = 0
    while count != pos-1:
        minVal = uglys.min
        if uglys.index(minVal*2)==nil:
            uglys.insert(-1,minVal*2)
        end
        if uglys.index(minVal*3)==nil:
            uglys.insert(-1,minVal*3)
        end
        if uglys.index(minVal*5)==nil:
            uglys.insert(-1,minVal*5)
        end

        uglys.delete(minVal)
        count += 1
    end

    puts minVal
end

ugly(1500)

두 번째 방법 ¶

로그를 이용. 로그를 이용하면 곱셈을 덧셈으로, 지수를 곱셈으로 치환가능. 예를 들어, 2, 3, 5대신, log2, log3, log5를 사용한다고 했을 때,

log2 = 0.3010
log3 = 0.4771
log5 = 0.6987

2 = log2
3 = log3
5 = log5

2*2 = 2^2 = (log2)^2 = 2*log2
2*3 = log(2*3) = log2 + log3
2*2*3 = log(2*2*3) = log2 + log2 + log3

가 되고 2^x*3^y*5^z 는 xlog2+ylog3+zlog5로 표현할 수 있다. log2, log3, log5는 상수이므로. 이는 3차원 공간상에서의 직선이 되는데, 이를 f(x,y,z)라고 하면, 정수 x,y,z에 대해 1500번째 위치에 있는 점을 구하고 이때의 x,y,z를 각각 2,3,5에 지수연산을 해 답을 구한다.

허나.. 더이상의 생각전개를 할 수 없다.

UglyNumbers, DamienRice