[프로그래머스] 점 찍기 (Lv. 2)

 

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

프로그래머스

 

---

 

범위 내 모든 좌표를 구하고, 

a==0 || b==0 인경우 각각 a*k <= d, b*k <= d 인 좌표갯수

a!=0 && b!=0 인경우 '각각의 제곱의 합 <= d의 제곱' 인 좌표갯수 (거리 이상인 좌표 제외)

 

 

package Programmers;

public class Coordinate {
	public static void main(String[] args) {

		int k = 1;
		int d = 5;
		int count = 0;
		
		
		for (int a = 0; a*k <= d; a++) {
			for (int b = 0; b*k <= d; b++) {
				if((a!=0 && b!=0) && Math.pow((a*k), 2) + Math.pow((b*k), 2) <= Math.pow(d, 2)) {
					System.out.printf("(%d , %d) ", a*k, b*k);
					count++;
				} else if (a==0 || b==0){
					System.out.printf("(%d , %d) ", a*k, b*k);
					count++;
				} 
			}
			System.out.println("");
		}
		
		System.out.println(count + "개");

	}

	
}

 

---

(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개

 

 

---

 

시간초과로 이중 for문 말고 다른 방법으로 해야 한단다....ㅎㅎㅎ

(a, b)의 갯수를 구한다고 하면,

a값의 최대를 먼저 구하고, 각 a값에 대한 b값의 최대를 구해서 k의 배수인 b의 갯수를 구한다.

* 정밀도를 위해 변수들의 데이터 타입을 int가 아닌 long으로 선언해줘야 한다 * 

 

package Programmers;

public class Coordinate {
	public static long solution(long k, long d) {
		
		int count = 0;
		long a = 0;
		
		for (int i = 0; i * k <= d; i++) {
			a = i * k;
			long b = (long) Math.sqrt(d*d - a*a);
			count += (int) (b / k) + 1;
		}
		return count;
		
	}
	
	
	public static void main(String[] args) {

		long result = solution(2, 4);
		System.out.println(result);	// 6

	}
}

 

---

 

answer 도 long타입으로 선언해줬더니 정답으로 인정

class Solution {
    public long solution(long k, long d) {
        
        long answer = 0;
        long a = 0;
        
        for(int i = 0; i * k <= d; i++){
            a = i * k;
            long b = (long) Math.sqrt(d*d - a*a);
            answer += (b/k) + 1;
        }
        
        return answer;
    }
}