[ 위클리 챌린지 ] [ 10주차 ] 교점에 별 만들기

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

코딩테스트 연습 - 10주차

 

---

풀이 과정

---

1. 각각의 선분들의 교점을 따로 저장해 둔다.
   1. 문제 아래의 수식을 기반으로 ad - bc가 0일때는 일치하거나 교점이 없는 경우이므로 생략하고 0이 아닐때만 교점 x,y를 구해준다.
   2. 교점 x, y가 정수가 아닌 경우는 저장하지 않아야 함 
      • 나머지 연산 사용
   3. x, y가 정수인 경우, 나중에 필요하기 때문에 최소 x,y 와 최대 x,y를 갱신시켜 준다.
2. 따로 1000 x 1000 배열을 만들어 둔 다음, 각각의 교점에서 최소 x, 최소 y를 빼준 지점에 * 표시를 해준다.
   • 교점들의 시작점을 모두 (0, 0)으로 설정한다고 생각하면 됨.
3. 이제 y의 범위를 (최대 y - 최소 y) ~ 0까지의 배열을 저장해주면 된다.
   • x의 범위는 (0 ~ 최대 x - 최소 x) 까지

• 헤맸던 점은.. 우선 교점 x,y가 정수가 아닌 경우도 고려해서 틀렸었고 다음으로 최댓값의 경우 초기값을 1000000000으로 해두어서 괜찮았는데, 최솟값을 0으로 두었다가 계속해서 틀린 문제점이 있었다. 최솟값도 -1000000000으로 두어 해결함.

---

소스 코드

---

def check(a, b, c, d):
    return (a*d) - (b*c) != 0

def get_xy(a, b, e, c, d, f):
    if ((b * f) - (e * d)) % ((a * d) - (b * c)) != 0 or \
       ((e * c) - (a * f)) % ((a * d) - (b * c)) != 0:
            return (-int(10e9), -int(10e9))
    
    x = ((b * f) - (e * d)) // ((a * d) - (b * c))
    y = ((e * c) - (a * f)) // ((a * d) - (b * c))
    
    return (x, y)

def solution(line):
    answer = []
    point_set = set()
    matrix = [['.'] * 1001 for _ in range(1001)] 
    min_x, max_x = int(10e9), -int(10e9)
    min_y, max_y = int(10e9), -int(10e9)
    
    for i in range(len(line)):
        for j in range(i):
            if check(line[i][0], line[i][1], line[j][0], line[j][1]):
                x, y = get_xy(line[i][0], line[i][1], line[i][2],
                             line[j][0], line[j][1], line[j][2])
                
                if x == -int(10e9):
                    continue
                
                if (x, y) not in point_set:
                    min_x, max_x = min(min_x, x), max(max_x, x)
                    min_y, max_y = min(min_y, y), max(max_y, y)
                    point_set.add((x, y))
    
    for x, y in point_set:
        if y - min_y <= 1000 and x - min_x <= 1000:
            matrix[y-min_y][x-min_x] = '*'
        
    max_y = max_y - min_y
    max_x = max_x - min_x
    
    for i in range(max_y, -1, -1):
        answer.append("".join(matrix[i][:max_x+1]))
        
    return answer