<프로그래머스> 두 원 사이의 정수 쌍(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EB%91%90%20%EC%9B%90%20%EC%82%AC%EC%9D%B4%EC%9D%98%20%EC%A0%95%EC%88%98%20%EC%8C%8D

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/181187#qna

제출 결과

 

붙잡고 있다보니 해결된 문제였다.

그리고 나름 간단하게 풀었나 싶었지만 다른 사람들의 풀이를 통과하고 나서 보니까 아직 멀었었다.

 

문제를 보자마자 든 생각은 '할 수 있나...?' 였다.

왜냐하면 숫자가 1000000까지 있었고 일반적인 방법인 모두 체크하기를 해버리면 시간초과가 바로 날 것 같았기 때문이다.

그렇게 고민을 하다가 4등분을 생각했다.

타원이 아니라 원이기 때문에 4등분을 했을 때 한쪽의 결과가 이외의 3부분의 결과와 동일하다.

그래서 한 곳을 구하고 곱하기 4하는 것으로 방향을 잡았다.

 

다음은 정수 좌표를 구하는 부분인데... 이건 큰 원 - 작은 원으로 방향을 잡고 시작했다.

뭔가 이 방법밖에 생각나지 않았다.

좌표축은 제외하고 이외의 공간을 x좌표를 기준으로 순회하면서 내림함수와 원의 방정식을 이용하여 정수 좌표 개수를 구했다.

그리고 큰 원 - 작은 원 하고 예제 통과하는 거 보고 제출했는데 틀렸다.

10개 중에 2개만 통과했다...

 

무엇이 문제일까 하고 반례를 찾아보다가 큰 수에서 원하는 결과가 나오지 않는 것을 볼 수 있었다.

입력값은 Int이지만 곱하기를 할 때 범위를 넘어가서 생기는 이슈가 발생한 느낌이 들어 번뜩 Long 타입 변환이 생각났다.

그래서 반지름 변수에 toLong()을 붙여주고 제출했는데 틀렸다.

10개 중에 6개 통과했다.

 

뭐가 문제인가... 하다가 생각해보니까 반복문의 i도 큰 수에서는 범위를 넘어간다는 걸 깨달았다.

그래서 i에도 toLong()을 붙여주고 제출했더니 맞았다.

 

이 문제를 풀 때 추가로 고려해야했던 것은 작은 원의 둘레에서 정수 좌표가 있는 경우였다.

둘레가 아닌 안쪽에 있으면 그냥 빼버리면 되지만 둘레에 있으면 추가해줘야 했다.

이걸 처리하기위해 y값에 내림함수를 한 것과 안 한 것이 같은지를 체크하는 조건문을 추가해줬다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import kotlin.math.floor
import kotlin.math.sqrt

class Solution {
    fun solution(r1: Int, r2: Int): Long {
        var answer: Long = 0

        var num2: Long = 0
        for (i in 1 until r2) {
            num2 += floor(sqrt((r2.toLong() * r2 - i.toLong() * i).toDouble())).toLong()
        }
        answer += r2 * 4 + 1 + num2 * 4

        var num1: Long = 0
        for (i in 1 until r1) {
            val count = sqrt((r1.toLong() * r1 - i.toLong() * i).toDouble())

            num1 += if (floor(count) == count) {
                floor(count).toLong() - 1
            } else {
                floor(count).toLong()
            }

        }
        answer -= (r1 - 1) * 4 + 1 + num1 * 4

        return answer
    }
}