프로그래머스 lv2 점찍기 코틀린 (kotlin)

11 December 2022 - 2 mins read time
Tags: 알고리즘 프로그래머스

문제

좌표상에 점을 찍는데 거리가 d 보다 작은 곳의 갯수를 세는 문제이다.

주의 해야할 점

숫자의 범위가 Int를 넘어갈 수도 있다는 점
이중반복문 사용시 1,000,000 * 1,000,000 ?

풀이 1 (이중반복문) 실패

import kotlin.math.pow
import kotlin.math.sqrt

fun solution(k: Int, d: Int): Long {
    var answer: Long = 0

    for (i in 0..(d/k)) {
        val longX = i*k
        for (j in 0..(d/k)) {
            val longY = j*k

            if (sqrt(longX.toDouble().pow(2.0) + longY.toDouble().pow(2.0)) <= d) {
                answer++
            }
        }
    }

    return answer
}

무지성으로 푼다면 나올 수 있는 모든 좌표 찾기
(0,0) - (x,y) 까지의 거리가 d 보다 작은지 체크하기

이중 반복문을 사용하면 k가 1이고 d 1,000,000 인 경우 1,000,000 * 1,000,000 을 수행해야 하므로 무조건 시간이 초과될 수 밖에 없다.

그렇다면 반복문을 하나 더 줄여야 한다.

풀이2 (하나의 반복문) 성공

import kotlin.math.pow
import kotlin.math.sqrt

fun solution(k: Int, d: Int): Long {
    var answer: Long = 0

    for (i in 0..(d/k)) {
        val longX = i*k
        val longY = (sqrt(d.toDouble().pow(2.0) - longX.toDouble().pow(2.0)) / k).toLong()

        answer += longY + 1L
    }

    return answer
}