프로그래머스 - 점 찍기

leehyunjon·2022년 12월 19일

수학 프로그래머스

Algorithm

목록 보기

146/162

점 찍기 : https://school.programmers.co.kr/learn/courses/30/lessons/140107#

Problem

Solve

첫번째 풀이

(x,y)에 대해서 원점부터의 길이는 d^2 = x^2 + y^2의 공식으로 구할 수 있습니다.
이를 통해서 y가 0일때, x가 d보다 작거나 같을때까지의 점 개수를 구해줍니다.

int a = 0;
while(k*a <= d){
	a++;
}

a는 d보다 큰 x의 좌표가 되기때문에 1을 빼주어 마지막 a값을 구해줍니다.

y좌표를 0부터 a까지 반복하면서
최대의 x좌표가 a이기 때문에, 각 y좌표에서 d보다 작거나 같은 x를 a의 값을 줄여가면서 조건을 만족하는 점의 개수를 answer에 저장을 반복해줍니다.

long answer = 0;	//점의 개수
a--;	//k와 곱해주기 위해 점의 개수에서 1을 빼줍니다.
int y = a*k;	//y의 최대값

for(int i=0;i<=y;i+=k){
	//현재y좌표 ^ 2 + 현재x좌표(a*l) ^ 2 가 d ^ 2보다 작거나 같은 경우를 찾을때까지 반복
	while(Math.pow(i,2) + Math.pow(a*k,2) > Math.pow(d,2){
    	//a감소
    	a--;
    }
    //조건을 만족하는 a를 점의개수를 맞춰주기 위해 1을 더해고 answer에 더해줍니다.
    answer += (a+1);
}

a값은 최대 x값보다 작거나 같기 때문에 항상 작아지게 됩니다. 그렇기 때문에 O(NlogN)의 시간복잡도로 해결할 수 있습니다.

통과는 했지만 문제 풀이가 너무 지저분하고 더 나은 풀이가 분명히 있을거라 생각하였습니다.

두번째 풀이

역시 이전풀이는 너무 직관적으로 생각한 풀이였고 더 나은 풀이가 있었습니다.

y좌표를 k만큼 증가시키면서 d^2 = x^2 + y^2의 공식에서 해당 y좌표에서 조건을 만족하는 x좌표를 찾기 위해 x^2 = d^2 - y^2로 변경하여 점의 개수(x/k + 1)를 찾게 된다면 훨씬 효율적으로 구현할 수 있었습니다.

이러면 O(N)으로 문제를 해결할수 있게 됩니다.

long answer = 0;
//y좌표
for(int y=0;y<=d;y+=k){
	//해당 y좌표에서 조건을 만족하는 x
	int x = (int)Math.sqrt((Math.pow(d,2)-Math.pow(y,2)));
    //해당 x좌표에서 k를 나누고 1을 더해주면 해당 좌표까지의 점 개수를 구할 수 있습니다.
	answer += (x/k)+1;
}

Code

첫번째 풀이

class Solution {
    public long solution(int k, int d) {
	    int a = 0;
	    while(k*a <= d){
	    	a++;
	    }

    	long answer = 0;
    	a--;
    	int y = a*k;
        
    	for(int i=0;i<=y;i+=k){
    		while(Math.pow(i,2)+Math.pow(a*k,2) > Math.pow(d,2)){
	    		a--;
	    	}
    		answer += (a+1);
    	}
    	return answer;
	}
}

두번째 풀이

class Solution {
    public long solution(int k, int d) {

		long answer = 0;
		for(int y=0;y<=d;y+=k){
            int x = (int)Math.sqrt((Math.pow(d,2)-Math.pow(y,2)));
            answer += (x/k)+1;
        }
		return answer;
	}
}