[프로그래머스] 교점에 별 만들기 (python)

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

프로그래머스

 

 

문제에서 주어진 교점 공식을 사용해보자.

 

문제 맨 밑에 참고사항을 보게 되면 아래와 같이 식이 하나 나와있다.

 

 

이 식을 코드로 표현하면 아래와 같다.

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])

교점을 모두 표현할 수 있는 최소한의 사각형을 알아내기 위해서는 교점인 좌표들을 보고 영점으로부터 가장 멀리 있는 좌표를 찾아 최댓값/최솟값을 계산하는 방식으로 대응하면 된다.

 

x_min = min(x_min, x)
y_min = min(y_min, y)
x_max = max(x_max, x)
y_max = max(y_max, y)

이제 위에서 구한 x값과 y값 교점들을 *로 표현하면 된다.

 

for문을 사용해 직접 할당하거나 리스트의 곱셈 또는 컴프리헨션 방식을 이용해 생성할 수 있다.

x_len = x_max - x_min + 1
y_len = y_max - y_min + 1
coord = [['.'] * x_len for _ in range(y_len)] # 2차원 리스트, '.'으로 초기화

for star_x, star_y in pos:
    # x_min이 음수일 경우 abs(x_min)을 더해 star_x를 그리드의 왼쪽으로 이동
    # x_min이 양수일 경우 x_min을 빼서 star_x를 그리드의 오른쪽으로 이동
    nx = star_x + abs(x_min) if x_min < 0 else star_x - x_min 

    # y_min이 음수일 경우 abs(y_min)을 더해 star_y를 그리드의 왼쪽으로 이동
    # y_min이 양수일 경우 y_min을 빼서 star_y를 그리드의 오른쪽으로 이동
    ny = star_y + abs(y_min) if y_min < 0 else star_y - y_min 
    coord[ny][nx] = '*'

결과로 나온 좌표값들을 하나의 문자열로 만든 다음 정답 배열에 넣어주면 된다. 정답 배열에 넣기 전 역순으로 변경해준다.

for result in coord:
    answer.append(''.join(result))

return answer[::-1]

전체 코드

def solution(line):
    pos, answer = [], []
    n = len(line)

    x_min = y_min = int(1e15)
    x_max = y_max = -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])
                x_min = min(x_min, x)
                y_min = min(y_min, y)
                x_max = max(x_max, x)
                y_max = max(y_max, y)

    x_len = x_max - x_min + 1
    y_len = y_max - y_min + 1
    coord = [['.'] * 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
        coord[ny][nx] = '*'


    for result in coord: answer.append(''.join(result))

    return answer[::-1]

    return answer;

 

 

 

references

programmers.co.kr

프로그래머스

 

product.kyobobook.co.kr

프로그래머스 코딩 테스트 문제 풀이 전략: 파이썬 편 | 김범수 - 교보문고