[프로그래머스] 점 찍기 [python]

문제

처음에 감이 안잡혀서, 힌트를 보았다,,,

원 안에 있는 점을 구하는 건데, 점은 k의 배수 또는 0 이어야 한다는 제약 조건이 있다.

x^2 + y^2 <= d^2 의 점 중에 위 제약 조건에 맞는 것을 구하면 된다.

처음에 가능한 모든 점을 구했다. k의 배수이고, 제곱이 d의 제곱 보다 작은 점들을 구했다.

그리고 한쪽은 가장 작은 곳 부터, 다른 한쪽은 가장 큰 쪽부터 두 수의 제곱이 d의 제곱보다 작은지 구했고,

크다면, (오른쪽의 값 -1)

작다면, (오른쪽의 값+1)을 answer에 더한후, (왼쪽 값+ 1) 해줬다.

왼쪽 기준으로 possibleDot에 있는 값 중 가장 큰 값을 구했기 때문에, 무조건 다음 값은 해당 값보다 작기 때문에, 위 같이 풀 수 있었다.

코드

def solution(k, d):
    answer = 0
    possibleDot = []
    i = 0
    while (i * k) * (i * k) <= d*d:
        possibleDot.append(i*k)
        i += 1
    i = len(possibleDot) - 1
    j = 0
    
    while j < len(possibleDot):
        if possibleDot[j] * possibleDot[j] + possibleDot[i] * possibleDot[i] > d*d:
            i -= 1
        else:
            answer += (i + 1)
            j += 1
    return answer
"""
두 양의 정수 k, d가 주어질 때 
x축: a*k, y축: b*k 만큼 떨어진 위치에 점을 찍는다
원점과 거리가 d를 넘는 위치에는 점을 찍지 않는다.
완점 탐색하면 안됨
"""