두 원 사이의 정수쌍 - 프로그래머스

김태훈·2023년 8월 22일
0
post-thumbnail

평가

결과: 2회 실패 후 성공
풀이: 50분
링크: https://school.programmers.co.kr/learn/courses/30/lessons/181187?language=java

해당 유형 많은 연습이 필요할 것 같습니다.
쉬운 난이도인데 이렇게 좌표에서 왔다갔다 하는 문제가 저는 참 어렵네요. 식을 정리해뒀는데 머릿속에서 좌표를 따라가다 보면 길을 잃어버립니다.

2번 다 틀린 이유는 엣지 케이스를 제대로 처리해주지 못해 발생했습니다.
내 풀이에서는 엣지 케이스들에 대한 처리가 필요한데 훨씬 쉬운 풀이가 있어 해당 풀이를 설명하는 걸로 대체하겠습니다.

해설

피타고라스의 정리를 사용해 풀 수 있습니다.
(x,y)가 두 원 사이에 들어가기 위해서는 아래와 같은 공식을 만족해야 합니다.

x^2 + y^2 <= 큰원반지름^2
작은원
반지름^2 <= x^2 + y^2

우리는 x좌표를 하나씩 살펴보면서 해당 x좌표에서 가능한 y값들의 개수를 구하려고 합니다.
따라서 위 식을 아래처럼 변환합니다.
y <= (큰원반지름^2 - x^2)
(작은원
반지름^2 - x^2) <= y

모든 x를 살펴보며 해당 식에 포함되는 y값들의 개수를 더해주면 됩니다.
주석을 따라가면 이해하실 수 있을 겁니다.

정답

import java.util.*;

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;

        for (long i = 0; i <= r2; i++) {
            if (i == 0) {
                answer += 2* (r2 - r1 + 1);
                continue;
            }
            long start = (long) Math.ceil(Math.sqrt((long) r1 * r1 - (long) i * i));
            long end = (long) Math.floor(Math.sqrt((long) r2 * r2 - (long) i * i));
            
            long temp = 0;
            
            // x값이 i일 때, y가 양수일때와 음수일 때 두 가지 케이스가 존재한다.
            temp = 2 * (end - start + 1);
            
            // start == 0이라는 건 x좌표에 있는 점이다.
            // 즉, y가 양수일때나 음수일때 똑같은 점이기 때문에 한 개를 빼줘야 한다.
            if (start == 0) {
                temp--;
            }
            
            // x가 양수일때와 음수일 때 두 가지 케이스가 존재한다.
            answer += (temp * 2);

        }

        return answer;
    }
}

내 풀이(비권장)

import java.util.*;

class Solution {
    public long solution(int r1, int r2) {
        long cnt = 0;
        cnt += calculate(r2);
        cnt -= calculate2(r1);
        return cnt;
    }
    
    // 반지름 r일 때, 안에 있는 점들의 개수를 구한다
    public long calculate(int r) {
        long cnt = 0;
        for(long i=0; i<=r; i++) {
            if (i==0) { //엣지케이스
                cnt += (2*r + 1);
                continue;
            }
            
            long temp = find(i, r);
            cnt += 2 * temp;
        }
        return cnt;
    }
    
    // x값이 i일 때, 가능한 y값의 개수
    public long find(long i, long r) {
        long low = 0;
        long high = r;

        while(low < high) {
            long mid = (low + high) / 2;
            
            if (mid * mid <= r * r - i * i) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return (low - 1) * 2 + 1;
    }
    
    public long calculate2(int r) {
        long cnt = 0;
        for(long i=0; i<=r; i++) {
            if (i==0) { //엣지케이스
                cnt += (2*r - 1);
                continue;
            }
            
            long temp = find2(i, r);
            cnt += 2 * temp;
        }
        return cnt;
    }
    
    public long find2(long i, long r) {
        if (i == r) {
            return 0;
        }
        long low = 0;
        long high = r;

        while(low < high) {
            long mid = (low + high) / 2;
            
            if (mid * mid < r * r - i * i) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return (low - 1) * 2 + 1;
    }
}
profile
작은 지식 모아모아

0개의 댓글