[프로그래머스 level2 교점에 별 만들기] 하나씩 확인하여 문제 해결하기

해결해야하는 문제는 다음과 같았다.

https://programmers.co.kr/learn/courses/30/lessons/87377

코딩테스트 연습 - 교점에 별 만들기

 

 

계속 프로젝트에 올인하다보니, 코딩테스트 문제를 안푼 지 오래된 것 같아서 오랜만에 풀어보았다.

 

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