프로그래머스 점 찍기

좀 쉬워보이는 문제를 골라보았다.

1/4 크기로 원을 그리면 그 안에 k 배수 단위로 찍을 수 있는 점의 갯수를 찾는 문제. 껌이네...

문제 설명

좌표평면을 좋아하는 진수는 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

입출력 예

k	d	result
2	4	6
1	5	26

입출력 예 설명

입출력 예 #1

• 본문의 예시와 같습니다.

입출력 예 #2

• (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (4, 0), (4, 1), (4, 2), (4, 3), (5, 0) 위치에 점을 찍을 수 있으며, 총 26개 입니다.

 

1차 시도

• 시간 초과 ㅋㅋㅋ
• 그치, 이게 맞지. 이렇게 쉬울리 없지.

from collections import Counter

def solution(k, d):
    s = []
    a = d // k + 1
    q = d ** 2
    for i in range(0,a*k,k):
        for j in range(i,a*k,k):
            t = i**2 + j **2
            if t <= q:
                s.append((i,j))
    ss = []
    for i in s:
        ss.append((i[1],i[0]))
    
    s = s + ss
    c = Counter(s)
    
    return len(c)
    
정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.1MB)
테스트 2 〉	통과 (0.05ms, 10MB)
테스트 3 〉	통과 (6453.82ms, 1.23GB)
테스트 4 〉	통과 (1848.45ms, 380MB)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	통과 (2221.76ms, 553MB)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	통과 (0.03ms, 10.2MB)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	통과 (0.05ms, 10.2MB)
테스트 16 〉	통과 (0.02ms, 10.1MB)

• 점을 직접 찍으면서 계산하면 안되고, 원 안에 찍을 수 있는 점을 찾아야 한다.
  • 삽입 삭제도 하지말고 그냥 카운트만 해야할 듯?

• 옛날에 했던 "Bresenham 알고리즘"에서 원 그리기 했던 거랑 비슷하네...
  • 브레즌햄 알고리즘은 컴퓨터 그래픽스에서 복잡하고 계산을 느리게 만드는 실수 계산을 배제하고 정수 계산만으로 직선을 그리기 위해 만들어진 알고리즘 입니다. 직선의 공식을 이용해 계산된 좌표값은 결국 스크린에 표현하기 위해서는 소수점 이하를 버림한다던지 반올림 해서 정수로 만들게 됩니다.
• 원을 그릴 때, 수평 수직으로 선을 긋는 방식이 있었는데 기억 안남.
• 넓이로 대충 나누면? 안됨 ㅋㅋ

import math

def solution(k, d):
    S = math.pi * d ** 2 / 4
    box = k**2
    answer = S // box
    print(S, box, answer)
    return answer

• 낄낄... 쉽게 될리가 없지 ㅡ.ㅡ;
• 원의 테두리만 계산하면 되지 않나?

import math

def solution(k, d):
    answer = 0
    a = d//k + 1
    for i in range(a):
        x = i * k
        y = math.sqrt(d**2 - x**2)
        c = y//k
        answer += c + 1
        #print("x:",x,"y:",y, "c:", c)
    
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (2.23ms, 10.2MB)
테스트 4 〉	통과 (1.22ms, 10.2MB)
테스트 5 〉	통과 (3.61ms, 10.2MB)
테스트 6 〉	통과 (3.10ms, 10.3MB)
테스트 7 〉	통과 (1.34ms, 10.2MB)
테스트 8 〉	통과 (30.01ms, 10.1MB)
테스트 9 〉	통과 (3.45ms, 10MB)
테스트 10 〉	통과 (6.45ms, 10.2MB)
테스트 11 〉	통과 (738.36ms, 10.4MB)
테스트 12 〉	통과 (0.01ms, 10.3MB)
테스트 13 〉	통과 (362.22ms, 9.98MB)
테스트 14 〉	통과 (228.01ms, 10.2MB)
테스트 15 〉	통과 (0.01ms, 10.1MB)
테스트 16 〉	통과 (0.01ms, 10.2MB)

• 고수의 풀이를 보니, math를 임포트할 필요가 없었군요.
• 난 왜 math를 임포트했지? ... 아... 원면적 계산해서 나누려고 pi 때문에 ㅎㅎㅎ

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

• 쉽네? (30분 넘게 걸림)