알고리즘 코드카타 116 - 점찍기

https://school.programmers.co.kr/learn/courses/30/lessons/140107

프로그래머스

문제 설명
좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.

원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.
원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.
예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다.

정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하세요.

 

제한사항
1 ≤ k ≤ 1,000,000
1 ≤ d ≤ 1,000,000

 

문제 자체는 어렵지 않았지만 주어진 범위가 아주 커서 시간복잡도를 해결하는 것이 문제였다.

 

def solution(k, d):
    answer = 0
    for x in range(0, d+1, k):
        for y in range(0, d+1, k):
            if (x ** 2 + y ** 2) ** 0.5 <= d:
                answer += 1
    
    return answer

 

처음으로 작성한 코드, 단순하게 모든 점을 순회하면서 조건에 맞는 점이 있을 경우 answer를 증가시켜서 조건에 맞는 점의 갯수를 세주었다. 당연히 시간초과로 실패했다.

 

def solution(k, d):
    answer = 0
    for x in range(0, d+1, k):
        for y in range(0, x+1, k):
            if (x**2 + y**2)**0.5 <= d:
                if x == y:
                    answer += 1
                else:
                    answer += 2
    
    return answer

 

두번째로 작성한 코드, 점이 찍히는 위치는 직선 x=y에 대해서 대칭이므로 탐색 조건을 바꿔서 x=y직선의 위쪽에 있는 점들만 세주었다. 직선과 겹치는 점은 1개만 세주고 겹치지 않는 점은 직선아래쪽에 있는 점까지 고려하여 2개를 세준다.

이전의 코드에 비해서 2배정도 빨라졌지만 이번에도 시간초과로 실패했다.

 

def solution(k, d):
    answer = 0
    range_d = d ** 2
    i = int(d**0.5)
    
    for x in range(i*2, d+1, k):
        for y in range(0, x+1, k):
            if x**2 + y**2 <= range_d:
                if x == y:
                    answer += 1
                else:
                    answer += 2
    
    return answer

 

세번째로 작성... 하려다 실패한 코드, 접근 방법은 d의 범위를 원으로 나타낼 수 있으므로 해당 범위에서 가장 큰 직사각형 부분을 따로 계산하고 직사각형과 원 사이에 있는 점을 따로 세 주어서 두 경우를 합쳐주는 것이었다.

위의 코드는 둘중 직사각형과 원 사이에 있는 점들의 갯수를 세주고 있으며 여기까지 작성하고 실행해보았을때 이미 시간초과가 발생했으므로 다른 방법을 찾기로 했다.

 

def solution(k, d):
    answer = 0
    
    for x in range(0, d+1, k):
        max_y = (d**2 - x**2)**0.5
        answer += max_y//k+1
    
    return answer

 

마지막으로 작성한 정답 코드, 점의 갯수를 모두 세주어야한다는 것이 문제였다. d+1보다 작은 특정 정수의 범위가 곧 점의 갯수가 되기 때문이다. 위의 코드는 x축 방향으로 점의 갯수를 세는데 y축을 전부 탐색하는 것이 아니라 해당 x값에서 조건에 맞는 범위에 속하는 y의 값의 갯수를 모두 구해준 뒤 answer에 추가하고있다.

드디어 성공!