이번에 다룰 내용은 직선 위의 최대 점 개수 구하기 입니다.
금년 4월 말 졸업 예정이기에 그 전에 취업을 위해 열심히 지원 서류를 작성하고 있습니다.
학교에서 제공하는 취업 컨설팅을 통해 추천 받은 Leetcode 라는 코딩 테스트를 위한 사이트를 추천받았습니다.
우리가 흔히 아는 백준과 동일한 역할을 하는 사이트지만 테스트 케이스를 수정하기에 용이하고 좀 더 편하다는
인상을 받았습니다.
취업 전까지 해당 사이트를 통해 반복 학습을 진행할 예정입니다.
해당 사이트에서 한 문제를 가져왔습니다.
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
x,y 좌표로 이루어진 점들이 주어졌을 때, 한 직선안에 있는 최대의 점 개수를 구하시오
해당 문제의 테스트 케이스는 다음과 같습니다.
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
추가적인 정보는 다음과 같습니다.
1 <= points.length <= 300
points[i].length == 2
-10^4 <= xi, yi <= 10^4
All the points are unique.
우선 처리해줘야 하는 정보들에 대해서 고려해 보아야 합니다.
추가 정보에서 모든 점들은 유니크 하다는 정보를 주었기 때문에 중복 되는 점에 대한 고려는 하지 않아도 됩니다.
주어진 점의 개수가 1인 경우엔 무조건 최대치가 1인것 또한 확인 해야합니다.
풀이 법은 간단합니다.
점들의 배열에서 두개를 골라 그 두 점의 기울기를 구하면 됩니다.
같은 한 점을 공유 하는 벡터의 기울기가 같다라는 것은 한 직선 위에 있다는 뜻이므로
한 점을 기준으로 잡고 나머지 점들과의 기울기를 구해 최대의 점 개수를 구하면 됩니다.
여기서 더 편한 코딩을 위해 defaultdict 라는 자료구조를 사용하겠습니다.
dictionary 와 동일한 구조를 가지고 있지만 차이점으로는 이미 할당되지 않은 키 값에 접근시에도 오류를 일으키지 않고
0으로 초기화된 값을 리턴합니다.
이를 통해 조금 더 편리하게 사용 가능합니다.
한가지 주의할 점은 기울기를 계산할 때 x값이 동일한 경우 기울기를 구할 수 없기 때문에
그 경우를 별개의 케이스로 분리해 계산 해 주어야 합니다.
from collections import defaultdict
class Solution:
def maxPoints(self, points):
if len(points) <= 1:
return len(points)
max_count = 0
for i in range(len(points)):
x1, y1 = points[i]
slopes = defaultdict(int)
vertical = 0
local_max = 0
for j in range(i + 1, len(points)):
x2, y2 = points[j]
if x1 == x2:
vertical += 1
continue
slope = (y2 - y1) / (x2 - x1)
slopes[slope] += 1
local_max = max(local_max, slopes[slope])
max_count = max(max_count, local_max + 1, vertical + 1)
return max_count해당 코드를 실행하여 결과를 확인 할 수 있습니다.
코딩 테스트 문제를 풀때 마다 느끼는 점이 어떻게 하면 효율적이고 좋은 구조의 로직을 구현 할까를 고민하는것도
중요하지만 어떠한 예외 사항이 있고 어떤 점을 주의해야 하는지 고민 하는 것 또한 중요한 부분임을
다시 한번 깨닫습니다.