2차원 배열 - 프로그래머스 교점에 별찍기

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

문제 풀어보기

문제 풀이의 흐름

직선이 주어지면

1. 주어진 직선에서 교점을 구한다
2. 그중 정수 교점만 따로 변수로 저장
3. 교점을 모두 표현할 수 있는 최소한의 사각형을 알아낸다
4. 모든 교점은 *을 찍어서 표현한다.
5. 배열을 거꾸로 뒤집어 반환한다.

직선의 개수가 10의 3승밖에 안되기 때문에 반복문을 중첩으로 사용해도 괜찮다

풀이

1. 주어진 직선에서 교점을 구한다

식 두개를 만들어서 교점을 구해야한다.

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)

첫번째 for문에서 가장 처음의 배열을 a,b,e에 할당하고 내부의 for문에서 나머지 배열들을 c,d,f에 할당하여 첫번째와 검사한다. 만약 평행이어서 교점이 없는 좌표라면 건너뛴다. 만약 교점이 있는 좌표라면 참고사항의 식을 사용하여 x와 y에 할당한다.

2. 그중 교점만 따로 변수로 저장한다

if x == int(x) and y == int(y):
                x = int(x)
                y = int(y)
                pos.append([x,y])

만약 소수점인 교점을 비교해야했다면 fractions나 decimal 라이브러리를 사용해야 했겠지만 이 문제에서는 정수인 교점만 비교하라고 했기 때문에 int로 형 변환을 하여 비교해준다.

3. 교점을 모두 표현할 수 있는 최소한의 사각형을 알아낸다

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_min = y_min = int(1e15)
x_max = y_max = -int(1e15)

최댓값과 최솟값은 이렇게 초기화 해준다. 최솟값을 찾을때는 가장 큰수로 초기화 해서 이것보다 낮은 수를 최솟값으로 설정하고 최댓값은 가장 작은수로 초기화 하여 이것보다 큰 수를 최댓값으로 설정한다.

4. 모든 교점을 *을 찍어서 표현한다.

# 행렬의 길이 측정
x_len = x_max - x_min + 1
y_len = y_max - y_min + 1
# 리스트 컴프리헨션
# .으로 2차원 리스트 초기화
coord = [['.'] * x_len for _ in range(y_len)]

# 음수 좌표를 찍어야하기 때문에 abs 사용
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
		# 파이썬 2차원 배열 리스트는 y가 먼저 오는것에 주의할 것
    coord[ny][nx] = '*'

음수좌표를 찍어야하기 때문에 두가지 방법이 있다.

1. 배열의 중앙을 (0,0)으로 생각하기
2. abs(절댓값) 연산을 통해 증가량을 표시하기

1번은 자잘한 보정이 필요하여 오답을 불러올 수 있기 때문에 2번으로 선택함

5. 거꾸로 뒤집기

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

return answer[::-1]

문자열로 묶어주고 거꾸로 뒤집어준다. 거꾸로 뒤집어주는 이유는 리스트에서는 인덱스가 클수록 아래에 위치하지만 좌표는 y값이 클수록 위에 위치해야하기 때문이다.

전체 코드

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