[프로그래머스 위클리 챌린지 10주차] 교점에 별 만들기

13번째로 풀이했습니다! 도움이 됐으면 MANGBAAM 좋아요 부탁드려요

전체 코드는 맨 밑에 있습니다

---

문제 설명

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

예를 들어, 다음과 같은 직선 5개를

• 2x - y + 4 = 0
• -2x - y + 4 = 0
• -y + 1 = 0
• 5x - 8y - 12 = 0
• 5x + 8y + 12 = 0

좌표 평면 위에 그리면 아래 그림과 같습니다.

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.

 

"..........."  
".....*....."  
"..........."  
"..........."  
".*.......*."  
"..........."  
"..........."  
"..........."  
"..........."  
".*.......*."  
"..........."

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

따라서 정답은

"....*...."  
"........."  
"........."  
"*.......*"  
"........."  
"........."  
"........."  
"........."  
"*.......*"

입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
  • line의 가로(열) 길이는 3입니다.
  • line의 각 원소는 [A, B, C] 형태입니다.
  • A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
  • 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
  • A = 0이면서 B = 0인 경우는 주어지지 않습니다.
• 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

직선 y = 1, x = 1, x = -1는 다음과 같습니다.

(-1, 1), (1, 1) 에서 교점이 발생합니다.

따라서 정답은

"*.*"

입니다.

입출력 예 #3

직선 y = x, y = 2x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은

"*"

입니다.

입출력 예 #4

직선 y = x, y = 2x, y = 4x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은

"*"

입니다.

---

참고 사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

---

나의 풀이

1. 두 직선의 교점 구하는 함수

우선 두 직선이 주어졌을 때 교점을 구하는 함수를 작성했다. 그 방법은 위에 참고 사항에 나와있기 때문에 그대로 구현했다.

def getIntCross(l1, l2):
    a, b, e = l1; c, d, f = l2
    if a*d - b*c == 0: return False
    x = (b*f - e*d) / (a*d - b*c)
    y = (e*c - a*f) / (a*d - b*c)

    return (int(x), int(y)) if x==int(x) and y==int(y) else False

만약 두 직선이 평행하거나 정수 값이 아니라면 False를 리턴하고, 그렇지 않다면 (x, y) 좌표를 리턴한다.

 

2. 교점 구하고 저장하기

def solution(line):
    cross = set()
    for a in range(len(line)):
        for b in range(len(line)):
            if a==b: continue
            point = getIntCross(line[a], line[b]) # 두 직선에 대한 정수인 교점
            if point: cross.add(point)

여러 직선들이 있을 때 같은 교점이 여러 번 나올 수 있으니 set() 자료형을 사용해 저장했다.

1.에서 작성한 getIntCross 함수로 두 직선의 정수 교점을 얻어왔고, if point 부분으로 False값이 리턴된 경우를 걸러냈다.

 

3. 별 찍기 준비하기

def solution(line):
    cross = set()
    
    # ... 2번 과정
    
    xs, ys = list(map(lambda x: x[0], cross)), list(map(lambda x: x[1], cross)) # x좌표, y좌표 분리

    startX, startY = min(xs), min(ys) # 0 이상으로 맞추기 위한 변수
    height = max(ys) - startY + 1 # 높이
    width = max(xs) - startX + 1 # 너비
    
    cross = list(map(lambda x: (x[0]-startX, x[1]-startY), cross)) # 0 이상으로 맞추기
    
    answer = ['.' * width for _ in range(height)]

우선 cross에 모인 여러 교점들 (x, y) 형태인 것을 x끼리, y끼리 분리해냈다.

그리고 x 좌표 중 가장 작은 값을 startX에, y 좌표 중 가장 작은 값을 startY에 저장했다.

그리고 y 좌표의 최고 값과 최저값의 차이 + 1 을 해서 그려야 할 높이를 구했고,

마찬가지로 x 좌표의 최고 값과 최저값의 차이 + 1 을 해서 그려야 할 높이를 구했다

startX와 startY를 구한 이유는 모든 x, y 값을 0 이상의 정수로 만들기 위함이다.

그리고 위에서 구한 width와 height를 바탕으로 answer이라는 리스트에 그림판(?)을 준비했다.

 

4. 별 찍기

def solution(line):
    cross = set()
    
    # ... 3, 4번 과정
  
    for x, y in cross:
        answer[y] = answer[y][:x]+'*'+answer[y][x+1:] # 별 삽입

각 행은 하나의 문자열로 이루어졌기 때문에 문자열을 슬라이싱해서 '*'을 삽입할 수 있다.

 

5. 리턴 시 주의사항

def solution(line):
    
    # ... 
    
    return answer[::-1]

 

 

리턴할 때 그대로 리턴하면 안되고 [ : : -1] 로 역순으로 리턴해야 한다.

왜냐하면 예시에서 주어진 좌표에서는 y 값이 클 수록 위로 올라간다. 하지만 파이썬 리스트의 인덱스는 그 값이 클 수록 아래로 내려간다.

그래서 우리가 4번에서 찍은 교점은 위 아래가 뒤바뀐 상태로 찍은 것이다.

문제의 의도대로 y 값이 클 수록 위로 찍히기 위해선 4번에서 찍은 값을 뒤집어주면 된다.

전체 코드

def solution(line):
    cross = set()
    for a in range(len(line)):
        for b in range(len(line)):
            if a==b: continue
            point = getIntCross(line[a], line[b]) # 두 직선에 대한 정수인 교점
            if point: cross.add(point)
    xs, ys = list(map(lambda x: x[0], cross)), list(map(lambda x: x[1], cross)) # x좌표, y좌표 분리

    startX, startY = min(xs), min(ys) # 0 이상으로 맞추기 위한 변수
    height = max(ys) - startY + 1 # 높이
    width = max(xs) - startX + 1 # 너비
    
    cross = list(map(lambda x: (x[0]-startX, x[1]-startY), cross)) # 0 이상으로 맞추기
    
    answer = ['.' * width for _ in range(height)]
  
    for x, y in cross:
        answer[y] = answer[y][:x]+'*'+answer[y][x+1:] # 별 삽입
    
    return answer[::-1] # 좌표는 y값이 클 수록 위로, python 인덱스에서는 y값이 클 수록 아래로

def getIntCross(l1, l2):
    a, b, e = l1; c, d, f = l2
    if a*d - b*c == 0: return False
    x = (b*f - e*d) / (a*d - b*c)
    y = (e*c - a*f) / (a*d - b*c)

    return (int(x), int(y)) if x==int(x) and y==int(y) else False

 

테스트 결과