프로그래머스 | LV.2 점 찍기 - 구현 문풀 (Java)

⬛ 프로그래머스 | LV.2 점 찍기 - 구현 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

일단 데이터 크기가 k와 d 모두 100만까지 들어오기 때문에 이중for문으로 돌면 시간초과가 뜬다. 1번의 for문 순회에서 모든 계산이 끝나야 하기 때문에 좌표 하나는 고정시켜두고 그에 대해 가능한 좌표개수를 카운팅하는 게 효율적인 처리다.

x든 y든 for문으로 가능한 값 순회하여 값 고정시켜두고, d 이하의 거리안에 가능한 정수 좌표 개수만큼 카운팅을 해야 된다.

풀이 예시

1) 시간을 더 줄이고 싶어서 List에 int 타입의 k배씩 최대 d까지 늘어나는 정수값을 하나 담아뒀다.

2) 이후 List의 각 x값에 대하여 거리 d를 만드는 x에 대한 y 최대 값을 구해두고,

3) 구한 최대 y값에 대한 카운팅 개수 누적해주면 된다.

 

💚 제출 코드

import java.util.*;
class Solution {
    //솔루션 함수 
    public long solution(int k, int d) {
        long answer = 0;
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<=d; i+=k){
            list.add(i);
        }
        
        for(int x : list){
            int maxY = (int) Math.sqrt(Math.pow(d,2) - Math.pow(x, 2));
            answer += (maxY)/k + 1;
        }
      
        return answer;
    }
}

💚 회고

아이디어까지는 냈는데 처음에 거리 d를 만드는 y에 대해 수식 처리를 단번에 떠올리지는 못했던 게 아쉬운 마음이 든다.