프로그래머스 87377 - 교점에 별 만들기

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

프로그래머스

1. 문제

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

별은 *으로 빈공간은 .으로 표현합니다.

모든 별을 포함하는 최소한의 크기만 표현합니다.

---

처음 문제집을 펴자마자 만날 수 있는 '교점에 별 만들기' 문제!

방정식을 보자마자 숨이 턱 막혔다. 그렇지만 이건 수학문제를 푸는 게 아닌 코딩테스트이기 때문에 문제에 힌트가 다 있다.

그래서 참고사항을 보면 교점을 구하는 방법이 있다. 

또한 정수 좌표에 별을 그리라는 힌트가 있으니 복잡하게 소수점을 생각할 필요가 없다.

 

2. 문제 풀이 흐름

1. 교점을 구한다.

2. 교점 좌표를 정수로 변환하고 변수에 따로 저장한다.

3. 별을 포함하는 최소한의 좌표를 구한다.

4. 모든 교점을 *로 표현한다.

5. 배열을 거꾸로 뒤집는다. ( 2차원 배열은 위에서 아래로 갈수록 인덱스값이 증가하는데 수학적 좌표계에서는 아래에서 위로 갈수록 y값이 증가한다는 개념 때문이다. )

 

def solution(line):
    pos, answer = [] , []#pos는 교점 담는 배열
    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: #ad - bc = 0 이면 평행이다. 
                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) #명시적 정수형 변환.(예를 들어, 소수점 아래가 0인 3.0같은 부동소수점을 3으로 변환)
                y = int(y)
                pos.append([x,y]) #교점을 pos에 담아줌
                #최솟값 최대값 구하기
                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 #모든 좌표값을 담기 위해 1을 더해준다.
    y_len = y_max - y_min + 1
    coord = [['.'] * x_len for _ in range(y_len)] #리스트 컴프리헨션로 2차원 생성

    for star_x, star_y in pos: #사각형 왼쪽 아래 꼭지점을 0,0으로 위치를 보정해준다.
        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] = '*' #'.'으로 2차원 생성해준것 위에다 *로 덮음.

    for result in coord: answer.append(''.join(result))
  
    print(answer[::-1])
    # return answer[::-1]

if __name__ == '__main__':
    solution([[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]])
    
#결과값
#['....*....', '.........', '.........', '*.......*', '.........', '.........', '.........', '.........', '*.......*']

 

꼭지점을 (0,0)좌표로 보정하는 것을 시각적으로 설명하는 그림

 

3. 배워갈 내용

✔️ 리스트 컴프리헨션

 [표현식 for 항목 in 반복가능객체 if 조건문] 

coord = [['.'] * x_len for _ in range(y_len)]

y_len의 수만큼(조건문)

['.'] * x_len 리스트를 반복(표현식)하여 포함하는 2차원 리스트를 생성한다.

예를 들어, x_len이 3이고 y_len이 2라면 최종 결과는 [ ['.', '.', '.'], ['.', '.', '.'] ]와 같은 형태로 리스트가 생성된다.

 

루프를 사용하는 것보다 리스트 컴프리헨션을 사용하는 것이 실행속도도 더 빠르고 코드도 간결해진다.

 

✔️최소값을 찾을 때는 매우 큰 값으로 초기화한다.

왜냐하면, 최소값을 찾을 때는 비교를 통해 값을 갱신하며 최소값을 찾아나간다.

매우 큰 값으로 초기화를 해놔야 첫 비교에서 즉시 값이 갱신될 수 있다.

최대값의 경우도 같은 원리다.

 

✔️2차원 배열은 위에서 아래로 갈수록 인덱스값이 증가하고 수학적 좌표계에서는 아래에서 위로 갈수록 y값이 증가한다. 

그래서 마지막에 배열을 뒤집어주지 않으면 틀린 답이 나오게된다.