[프로그래머스,java] 두 원 사이의 정수 쌍

 

 

 

그냥  원 사이의 정수 쌍 구하는 문제가 2레벨에 있었던거같은데, 

 

두 원 사이의 정수쌍을 구하는 문제가 나왔다.. (이게 같은 2레벨?)

코딩테스트가 점점 난이도가 높아져가 수능이되어간다..;

 

 

 

문제분석 

 

일단,  하나의 원 안쪽에있는 정수쌍을 구하는법은, 

 

피타고라스의식  x^2+y^2 = r^2 을 쓰면된다.  이것도 기출을 파악해야 바로 떠오르지,  안풀어본사람은 떠오르기 힘들엇을것같다.

 

그 이유는, r은 문제에서 주었고,  X를 0~r 까지 탐색한다 가정하면,  y의 갯수가 추정이된다.

 

즉,  y^2= r^2- x^2  (x는 0부터 r까지 인덱스값) 

 

이렇게 식을짜면, x가 0, 1 , 2 ..일때 가능한  y의 0 ,1 , 2의 갯수가 나오게된다.

 

 

=> 헌데 이게 그냥 원 한개의 테두리 포함 문제였다면 쉽겟지만,  두 원이 겹쳐진 경우는 좀 애기가 다르다.

 

 

그냥  r2 원에서구한 쌍갯수 -  r1원에서 구한 쌍갯수 하면 되는거 아닌가? 라고 생각하지만 안된다 이게.. 

 

 

그 이유는, 당장 그림의 y=0축을 보면,  r2 가 3이면 내부의 정수쌍 3개,  r1가 2이면 2개다.

 

근데, 점수를찍힌걸보면, 3-2=1이다.  문제는 테두리도 포함이라서, 2개인데 엄연히 다르다.

 

또한,  5^2 = 4^2+3^2 처럼   x축 y축 뿐만아닌, 1사분면내부에서도 정수쌍이 테두리에 딱 맞는케이스가 존재할수있다.

 

=> 이 경우를 고려해야한다.  

 

문제풀이

 

import java.util.*;
class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
 
        
        long r1x = (long)Math.pow(r1,2);
        long r2x = (long)Math.pow(r2,2);
        
        //y^2= r^2-x^2
        
        long y1sum=0;
        long y2sum=0;
        long side =0;
        
        for(long i=0;i<=r2;i++){
           
          
           long y2 = (long)Math.sqrt(r2x-(long)Math.pow(i,2));
        
           long y1 = (long)Math.sqrt(r1x-(long)Math.pow(i,2));
            
           // 이 부분 추가!
           if(Math.sqrt((r1x-Math.pow(i,2)))%1==0){
               side++;
           }
          
            answer+=(y2-y1)*4;
        }
      
        answer+=side*4-4;
        
  
        
        return answer;
    }
}

 

필자는 , 테두리부분을 체크하는 side를 구한뒤에,  중복되는걸 빼주었다.

 

 

근데 역시 언제나 최적화하신 풀이가 있는법...

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
 
        for (int i=1; i<=r2; i++) {
            long minJ = (int) Math.ceil(Math.sqrt(1.0*r1*r1 - 1.0*i*i));
            long maxJ = (int) Math.floor(Math.sqrt(1.0*r2*r2 - 1.0*i*i));
 
            answer += (maxJ - minJ + 1);
 
        }
 
        return answer * 4;
    }
}

 

테두리 체크하는걸  ceil인 올림과,  floor 내림을 사용하여 체크한 다른사람의 풀이가 있다.

 

아주 훌륭하고 가독성도 뛰어난 풀이같다.