코딩테스트 연습 - 교점에 별 만들기
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, -
programmers.co.kr
2차원 평면상의 좌표와 2차원 배열의 좌표를 구하는데 시간이 오래 걸렸던 문제다.
알고리즘은 다음과 같다.
1. ad-bc != 0이 아닌 조건을 통해 교점을 구하고, 정수로 나타낼 수 있는 교점일 경우 교점 리스트에 추가해준다.
2. 교점의 집합에서 x, y 좌표의 최댓값과 최솟값을 구해서 2차원 배열을 초기화시켜준다.
3. 2차원 평면상의 좌표를 2차원 배열의 좌표로 찍어내려면
x, y = abs(y_max-b) , abs(x_min-a)의 공식으로 구할 수 있다.
코딩테스트 연습 - 10주차
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, -
programmers.co.kr
문제에 제시된 참고사항을 참고해 두 직선의 모든 좌표가 정수인 교점을 구하는 함수 intersection_point를 만들었다.
solution 함수에선 입력으로 주어진 모든 직선을 2개씩 짝지어 교점을 구하고, 이들을 points라는 집합에 저장했다. 각 교점의 x좌표의 최대, 최솟값과 y좌표의 최대, 최솟값을 구해 최종 반환값의 크기를 파악했다. 이 크기에 맞게 우선 . 으로 초기화하고, 각 점을 하나씩 확인하면서 해당하는 위치에 *을 그려준다.
해결해야하는 문제는 다음과 같았다.
//programmers.co.kr/learn/courses/30/lessons/87377
코딩테스트 연습 - 교점에 별 만들기
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, -
programmers.co.kr
계속 프로젝트에 올인하다보니, 코딩테스트 문제를 안푼 지 오래된 것 같아서 오랜만에 풀어보았다.
Ax + By + E = 0
Cx + Dy + F = 0
가 인풋으로 주어진다.
ad-bc=0이면, 일치하거나 평행인 경우이고, x,y값은 다음과 같이 구할 수 있다.
1. pos : 교점의 좌표를 담을 배열, answer : 별좌표를 담을 배열, n : 주어지는 직선의 개수를 선언한다.
2. x_min, x_max, y_min, y_max 를 초기화한다.
3. line을 하나씩 검토하며, 두 개의 Line의 교점을 찾는다.
-> 평행인 경우 continue하여 검사하지 않고,
-> x,y가 모두 정수라면 교점의 좌표를 answer에 저장한다.
-> 좌표 저장 시, x_mi, x_max, y_min, y_max 값을 업데이트해준다.
4. 격자판 중 최소한의 크기만 나타내면 되므로, 교점의 x,y 범위를 구하여 x_len, y_len에 담는다.
5. arr에는 2차원 배열 형태로 . 혹은 * 좌표를 저장할 수 있도록 한다.
처음부터 아래와 같은 방식으로 저장하는 경우,다음과 같은 오류를 마주할 수 있다.
["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
arr[ny][nx]='*'
TypeError: 'str' object does not support item assignment
따라서 arr은 우선 이렇게 정의되도록 하였다.
[['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.']]
6. 저장된 교점 좌표를 순회하며, 배열의 어느 부분에 들어가야 하는지 계산한 후, 해당 점을 "*"로 변환하였다.
for star_x, star_y in pos: nx = star_x + abs(x_min) if x_min < 0 else star_x - x_min ny = star_y + abs(y_min) if y_min < 0 else star_y - y_min arr[ny][nx]='*'7. .join함수를 통해 리턴해야하는 값을 answer 배열에 저장해준다.
['.', '.', '.', '.', '.', '.', '.', '.', '.'] -> ['.........']
for i in range(len(arr)-1,-1,-1): answer.append(''.join(arr[i]))여기서 주의할 점은 거꾸로 담는다는 점이다.
2차원 좌표계에서는, 왼쪽이 -값, 오른쪽이 + 값이라는 점은 동일하지만,
일반 행렬에서 위로 갈수록 작은 값이고 아래로 갈수록 큰 값인 것과 반대로 -> 위로 갈수록 큰 값, 아래로 갈 수록 작은 값이라는 것을 주의해야 한다!!
min값과 max값을 -int(1e9), int(1e9)로 초기화하였을 때, 27,28번 테스트케이스에서 오류가 났다. 범위가 굉장히 커서 오류가 날 수 있다는 것을 보고, int(1e15), -int(1e15)으로 초기화하니 잘 돌아갔다!!
아이디어를 바탕으로 작성한 코드는 다음과 같다.
def solution(line): pos = [] answer = [] n = len(line) x_min, y_min = int(1e15),int(1e15) x_max, y_max = -int(1e15), -int(1e15) for i in range(n): a,b,e = line[i] for j in range(i+1,n): c,d,f = line[j] if a*d == b*c : continue x = (b*f-e*d) / (a*d-b*c) y = (e*c-a*f) / (a*d-b*c) if x == int(x) and y == int(y): x = int(x) y = int(y) pos.append([x,y]) if x_min > x : x_min = x if y_min > y: y_min = y if x_max < x: x_max = x if y_max < y : y_max = y x_len = x_max-x_min+1 y_len = y_max-y_min+1 arr = [['.']*x_len for _ in range(y_len)] for star_x, star_y in pos: nx = star_x + abs(x_min) if x_min < 0 else star_x - x_min ny = star_y + abs(y_min) if y_min < 0 else star_y - y_min arr[ny][nx]='*' for i in range(len(arr)-1,-1,-1): answer.append(''.join(arr[i])) return answer