문제1 - 교점에 별 만들기 (Python)

프로그래머스

 

여러 직선의 방정식이 주어졌을 때, 모든 정수 교점을 찾아 이를 포함하는 최소 크기의 사각형 도화지에 별을 그리는 문제입니다. 좌표계의 특성과 정밀한 수치 연산이 핵심입니다.

---

1.  나의 풀이 (Modular Approach)

기능별로 함수를 분리하여 가독성을 높였습니다. 한 줄이 길어질 수 있는 연산은 변수를 활용해 코드 블록 형태로 나누어 작성했습니다.

def get_cross_point(a, b, e, c, d, f):
    # 분모 계산을 통한 평행 여부 확인
    denominator = a * d - b * c
    if denominator == 0:
        return None
    
    # 정수 교점 여부 확인 (나머지 연산 활용)
    x_numerator = b * f - e * d
    y_numerator = e * c - a * f
    
    if x_numerator % denominator != 0 or y_numerator % denominator != 0:
        return None

    # 정수 좌표 반환
    x = x_numerator // denominator
    y = y_numerator // denominator
    return x, y


def convert_zero_based_star_with_max_point(points, min_xy):
    # 최소값을 0으로 맞추기 위한 bias 설정
    x_bias = -min_xy[0]
    y_bias = -min_xy[1]

    # 시작점 기준 최대값 초기화
    x_max = x_bias + points[0][0]
    y_max = y_bias + points[0][1]

    zero_based_star = []
    for point in points:
        # 좌표 평행 이동
        converted_point = (point[0] + x_bias, point[1] + y_bias)
        zero_based_star.append(converted_point)
        
        # 도화지 크기 결정을 위한 최대값 갱신
        if converted_point[0] > x_max:
            x_max = converted_point[0]
        if converted_point[1] > y_max:
            y_max = converted_point[1]

    return zero_based_star, (x_max, y_max)


def convert_star_text(star_point, size):
    # .으로 초기화된 도화지 생성
    width = size[0] + 1
    height = size[1] + 1
    star_text = [["."] * width for _ in range(height)]
    
    # 별 위치 기록
    for point in star_point:
        star_text[point[1]][point[0]] = "*"

    # 수학 좌표계와 리스트 인덱스의 Y축 반전 처리
    star_text.reverse()

    return list(map("".join, star_text))


def solution(line):
    points = set()
    minx, miny = None, None

    # 모든 직선 쌍에 대해 교점 계산 (중복 방지 순회)
    for i in range(len(line)):
        for j in range(i + 1, len(line)):
            p = get_cross_point(
                line[i][0], line[i][1], line[i][2],
                line[j][0], line[j][1], line[j][2]
            )
            
            if p is not None:
                # 사각형 범위를 위한 최소 좌표 추적
                if minx is None or minx > p[0]:
                    minx = p[0]
                if miny is None or miny > p[1]:
                    miny = p[1]
                points.add(p)
                
    points_list = list(points)
    # 0,0 기반 좌표 변환 및 텍스트 생성
    star_point, size = convert_zero_based_star_with_max_point(
        points_list, (minx, miny)
    )

    return convert_star_text(star_point, size)

---

2.  오늘 배운 점 및 복기 노트

나머지 연산자를 이용한 정수 검증
나눗셈 결과인 실수를 int()와 비교하는 대신, 나누기 전 나머지 연산(%)으로 나누어 떨어지는지 확인하는 것이 부동소수점 오차를 방지하는 가장 안전한 방법임을 확인했습니다.

조합 최적화 루프
range(i + 1, len(line))를 사용한 루프 설계는 동일한 직선 쌍에 대한 중복 계산을 배제하여 연산 효율을 높여줍니다.

좌표계 평행 이동(Bias) 전략
음수 좌표를 배열 인덱스로 변환하기 위해 최소 좌표값을 기준으로 전체 좌표를 평행 이동시키는 방식은 코드의 직관성을 높여줍니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

문자열 결합 시 join() 활용의 중요성
파이썬에서 + 연산자로 문자열을 반복해서 합치면 매번 새로운 객체가 생성되어 메모리와 성능에 악영향을 줍니다. 대량의 문자열 배열을 처리할 때는 반드시 "".join()을 사용하는 습관을 들여야 합니다.

실시간 최솟값/최댓값 추적의 효율성
교점을 다 구한 뒤 다시 순회하며 범위를 찾는 것이 아니라, 교점이 발생하는 즉시 최솟값과 최댓값을 갱신하여 별도의 루프 비용을 제거하는 방식이 성능 최적화에 유리합니다.

부동소수점 오차에 대한 경계
컴퓨터의 이진법 체계로 인해 발생하는 0.1 + 0.2 != 0.3과 같은 한계를 지적하며, 정밀한 기하학 문제에서는 정수 기반 연산을 최우선으로 고려해야 합니다.