-
문제 설명
-python dictionary 사용 불가
-N개의 점 (x, y) 좌표가 입력으로 주어질 때, 4개 이상의 점을 연결하는 maximal한 직선을 모두 찾아라.
-정렬을 활용하라. 각 점 p에 대해, p가 다른 모든 점과 이루는 기울기를 계산해, 기울기를 key로 정렬한다. 정렬 결과에서 3개 이상의 인접한 점이 같은 기울기를 갖는다면, 이들은 collinear points다. -
구현 방법
-입력 points: xy 좌표계에 속한 점의 list
points는 tuple (x, y)의 리스트. 예) [(3,2), (4,-1), (0,0), (-2,2)]
points에 속한 점은 모두 좌표가 서로 다름. 즉, x,y값이 둘 다 일치하는 점은 주어지지 않는다.
-반환값: 4개 이상의 점을 연결하는 maximal한 직선 모두를 리스트에 담아 반환.
양 끝이 p, q인 직선(p<q)은 양 끝점 좌표를 4-tuple (px, py, qx, qy) 형식으로 나타낸다. 이때, 두 점 중 더 작은 점이 p, 더 큰 점이 q이다.
두 점의 대소 관계를 따질 때는 x좌표 먼저 비교하고, x좌표가 같으면 y좌표를 비교한다.
둘 이상의 직선을 반환할 때는 px 작은 직선 먼저 반환하며, px가 같다면 py->qx->qy 순으로 비교한다.
정렬을 위해서 sorted() 또는 list.sort() 함수를 활용한다.
-기울기 계산 결과에서 소수점 6자리 아래는 math.floor(p*1000000/1000000 사용)해서 절삭한다.
-x축과 평행인 직선의 기울기는 0, y축과 평행인 직선의 기울기는 float('inf') -
Python 코드
def collinearPoints(points): #(x,y) 형태의 점들의 리스트를 인자로 받음
def check(a, b): #점 a 점b 사이의 기울기 계산하는 함수
if b[1]-a[1] == 0: #두 점의 y값이 같으면
return 0 #기울기 0
elif b[0]-a[0] == 0: #두 점의 x값이 같으면
return float('inf') #기울기 무한대
else: #그 외의 경우
return (b[1]-a[1]) / (b[0]-a[0]) #기울기 반환
answer = [] #최종적으로 반환할 결과 리스트 (collinear points 선분의 양 끝점을 4-tuple 형태로 저장)
points.sort(key=lambda x: (x[0], x[1])) #입력받은 점들을 x좌표 기준으로 정렬, x좌표 같다면 y좌표 기준으로 정렬
for i in range(len(points)): #모든 점들을 하나씩 반복, i=현재 처리 중인 점
li = [] #현재 점(points[i])과 다른 모든 점들과의 정보를 저장하는 리스트
for j in range(len(points)): #다른 모든 점들에 대해 반복
if i != j: #현재 처리 중인 점 points[i]와 자기 자신을 비교하지 않도록
li.append([points[j][0], points[j][1], check(points[i], points[j])]) #li 리스트에 현재 점 points[j]의 x좌표, y좌표 및 check 함수로 계산한 기울기 추가
li.sort(key=lambda x: x[2]) #li 리스트를 기울기(x[2]) 기준으로 정렬
cnt = 0 #현재 같은 기울기를 가지는 점의 개수 (초기값 0으로 설정)
cur = li[0][2] #현재 처리 중인 기울기. (초기값은 li리스트의 첫번째 요소의 기울기로 설정)
for j in range(1, len(li)): #기울기가 다른 모든 점들에 대해 반복
if li[j][2] == cur: #만약 현재 점의 기울기가 이전과 같다면,
cnt += 1 #cnt 1 증가
if j == len(li) - 1 and cnt >= 2: #만약 현재 점이 리스트의 마지막이고, cnt가 2이상이라면, 세 개 이상의 점이 동일한 선분 위에 있는 것
ans = [[points[i][0], points[i][1]], [li[j][0], li[j][1]], [li[j-cnt][0], li[j-cnt][1]]] #공통 선분을 이루는 점들을 ans 리스트에 저장
ans.sort(key=lambda x: (x[0], x[1])) #ans 리스트를 x좌표 기준으로 정렬, x좌표 같다면 y좌표 기준으로 정렬
ans2 = (ans[0][0], ans[0][1], ans[2][0], ans[2][1]) #공통 선분의 끝점을 나타내는 튜플
if ans2 not in answer: #answer 리스트에 이러한 선분이 아직 추가되지 않았다면,
answer.append(ans2) #answer 리스트에 ans2 추가
else: #만약 현재 점의 기울기가 이전과 다르다면,
if cnt >= 2:
ans = [[points[i][0], points[i][1]], [li[j-1][0], li[j-1][1]], [li[j-1-cnt][0], li[j-1-cnt][1]]]
ans.sort(key=lambda x: (x[0], x[1]))
ans2 = (ans[0][0], ans[0][1], ans[2][0], ans[2][1])
if ans2 not in answer:
answer.append(ans2)
cnt = 0 #현재 점부터 새로운 공통 선분을 찾기 위해 cnt 초기화
cur = li[j][2] #cur 초기화
return answer #answer 리스트 반환