23.02.14 파이썬 코딩 퀴즈#154 점 찍기 (프로그래머스 스쿨)

이번 문제는 점 찍기 문제이다.

전달받은 두 양수 k, d 를 이용해서 좌표평면 위에 점을 찍고, 그 점의 갯수를 반환해야 한다.

예를 들어 k는 2, d 가 4인 경우라면 원점(0,0)으로 부터 좌표는 (a*k, b*k) 의 형태(k의 배수) 이며 거리가 d를 넘어가는 위치에는 점을 찍을 수 없다. 즉 거리가 d 이하인 위치만 가능하다.

굉장히 간단하게 작성해 본 첫번째 코드.

k의 배수만 가능하기에 애초에 반복문 조건으로 k 만큼 건너 뛰도록 구현하였다.

원점과의 거리 확인은 피타고라스 정리를 활용하여 계산하였다.

결과는 50점... 역시나 시간 초과에서 걸린다.

이번엔 생각의 전환이다. 먼저 점이 찍히는게 가능한 모든 좌표의 x,y 값을 구한 다음 그 개수를 answer에 전달 한 뒤, 점의 위치가 거리 d를 초과하는 값들만 answer에서 빼주었다. 그 다음 초과하지 않는 x좌표가 나오면 해당 x 좌표에 대한 탐색을 중단하는 방법으로 코드를 작성 하였다.

처음보단 빨라졌지만, 여전히 시간 초과에 걸린다.

그리고 마지막 코드.

먼저 for문을 통해 가능한 y 의 최대값을 먼저 구한뒤, 0 부터 y 까지 k 번으로 뛰어서 몇개가 존재하는지를 확인하였다.

예를 들어 y가 6이고 k 가 2 라면, 실제 y 값은 0,2,4,6 4개가 된다. 이처럼 나누어 떨어지는 경우는 +1을 해주고,

math.ceil()에 의해 올림 처리되는 경우는 그냥 그 값을 answer에 전달한다.

문제 설명과 풀이에 비해 상당히 까다로운 문제였다.