[프로그래머스] lv2. 교점에 별 만들기 (Python 3)
❓ 문제
코딩테스트 연습 - 교점에 별 만들기 | 프로그래머스 스쿨 (programmers.co.kr)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
✏️ 나의 풀이
💡 해결하기
입력으로 주어지는 리스트 line의 각각의 요소들로 하나씩의 직선의 방정식을 만들 수 있다.
따라서 line의 요소들을 직선 하나씩으로 생각할 수 있고, 직선 2개씩의 교점을 확인하는 식으로 문제를 풀어나간다.
코드 작성 순서는 다음과 같다.
1.
def solution(line):
answer = []
vertex = set()
답은 리스트 안에 담겨서 나와야 하므로 빈 리스트를 값으로 가지는 answer 변수를 선언해 주었다. 나중에 점과 별로 이루어진 문자열로 answer 리스트를 채울 것이다.
vertex는 '교점'을 의미하는 변수이다.
위에서 직선 2개씩의 교점을 확인하는 방식으로 문제를 푼다고 했는데, 꼭 직선 2개에서의 교점만 존재하는 것이 아니고 직선 3개, 4개에서의 교점도 존재할 수 있다. 직선 2개에서의 교점을 구하는 방식으로 풀 시 위와 같은 경우는 중복되는 교점으로 나타날 것이므로 set()을 통해 중복을 없애줄 수 있다. 후에 적용하지 않고, 미리 vertex에 set을 선언해 주었다.
2.
from itertools import combinations
....
for line_1, line_2 in combinations(line, 2):
if checkSlopeDifferent(line_1, line_2):
if getIntVertex(line_1, line_2) != None:
vertex.add(getIntVertex(line_1, line_2))
1번의 코드에 이어 적은 코드이다.
line 리스트에서 중복되지 않게 2개의 요소(직선)를 고르는 모든 경우의 수를 구하기 위해 itertools 모듈의 combinations(조합) 함수를 사용해 주었다.
combiantions를 사용하기 위해서는 'from itertools import combinations"를 적어 모듈을 불러와야 하는 것을 잊지 말자.
2개의 요소가 묶이게 되고, 그 요소를 각각 line_1이라는 변수와 line_2라는 변수에 할당해 주었다.
그리고 checkSlopeDifferent이라는 함수를 통해 line_1안의 요소로 만든 직선의 기울기와 line_2 안의 요소로 만든 기울기가 같은지를 체크한다.
기울기가 같다는 것은 두 직선이 평행하거나 일치한다는 의미이다.
checkSlopeDifferent 함수의 반환값이 True일 경우, getIntVertex 함수에서 결괏값이 None이 아니라면 vertex에 getIntVertex(line_1, line_2)의 값을 추가해 줄 것이다.
(* set 자료구조에서는 요소를 추가할 때 append가 아닌 add를 사용해야 한다.)
문제 하단에 나와 있는 참고 사항인데, 이 참고 사항의 식을 이용하여 checkSlopeDifferent 함수와 getInVertex 함수의 실행문을 작성할 것이다.
3.
def checkSlopeNotSame(line_1, line_2):
a, b, e = line_1
c, d, f = line_2
if a * d - b * c == 0:
return False
return True
우선, checkSlopeDifferent 함수 작성 과정이다.
각 직선의 x의 계수와 y의 계수가 모두 필요하므로 line_1과 line_2를 모두 인자로 받았다.
참고사항에 주어진 공식에 맞추기 위해 line_1의 각 요소들은 차례로 a, b, e 변수에 할당해 주었고, line_2의 각 요소들은 차례로 c, d, f에 할당해 주었다.
공식에 따라 조건문을 작성해 주었고, 결과가 0일 경우 False (두 직선은 교점이 생기지 않음), 0이 아닐 경우 True (두 직선은 교점이 생김)를 반환하도록 하였다.
4.
def getIntVertex(line_1, line_2):
a, b, e = line_1
c, d, f = line_2
x = (b*f - e*d) / (a*d - b*c)
y = (e*c -a*f) / (a*d - b*c)
if x.is_integer() and y.is_integer():
return (int(x), int(y))
getIntVertex 함수의 작성 과정이다.
마찬가지로 참고사항에 나와 있는 대로 공식을 적용하기 위해 checkSlopeDifferent 함수 때와 동일한 방식으로 변수에 값을 할당해 주었다.
x 절편과 y 절편을 공식대로 구하여 각각 변수 x와 y에 할당해 주었다.
그리고 x와 y가 모두 정수일 경우에만 vertex에 넣고 싶으므로 is_integer() 메서드와 and 논리 연산자를 이용하여 확인하는 과정을 작성하였고, 추후 값 활용을 위해 float type인 x와 y를 int type으로 변환해 주었다.
5.
def solution(line):
answer = []
vertex = set()
for line_1, line_2 in combinations(line, 2):
if checkSlopeDifferent(line_1, line_2):
if getIntVertex(line_1, line_2) != None:
vertex.add(getIntVertex(line_1, line_2))
여기까지만 살펴보면, vertex에 x 좌표와 y 좌표가 모두 정수로 이루어진 교점이 {(x, y).....} 의 형식으로 들어 있어야 한다.
set을 사용했으므로 중복되는 교점은 없다.
6.
sort_x = sorted(list(vertex))
min_x = sort_x[0][0]
max_x = sort_x[-1][0]
위 코드에 이어서 작성한다.
sort_x는 vertex를 list로 변환한 것을 x좌표 기준으로 오름차순 정렬한 리스트이다.
추후 점과 별을 찍을 때 사용하기 위해 수가 가장 작은 x 좌표인 min_x와 수가 가장 큰 x 좌표인 max_x를 미리 구해두었다.
오름차순이므로 가장 작은 x 좌표는 sort_x 리스트의 맨 앞쪽에 위치하고, 가장 큰 x 좌표는 sort_x 리스트의 맨 뒤쪽에 위치한다.
7.
sort_y = sorted(list(vertex), key = lambda x: x[1])
max_y = sort_y[-1][1]
min_y = sort_y[0][1]
sort_y는 vertex를 list로 변환하느 것을 y좌표 기준으로 오름차순 정렬한 리스트이다.
이 또한 점과 별을 찍을 때 사용하기 위해 같은 방식으로 max_y와 min_y를 구해두었다.
8.
for i in range(max_y, min_y-1, -1):
dot = ['.'] * (max_x - min_x + 1)
while True:
if len(sort_y) != 0:
if sort_y[-1][1] == i:
dot[sort_y[-1][0] - min_x] = '*'
sort_y.pop()
else:
break
else:
break
answer.append(''.join(dot))
마지막으로, 점과 별을 찍는 단계이다.
i는 y좌표가 될 수 있는 수를 의미한다. 범위를 max_y부터 min_y까지 1씩 감소해 가는 것으로 정했다.
y좌표가 가장 큰 별이 존재하는 위치부터 y좌표가 가장 작은 별, 즉 끝나는 위치까지만 찍어야 하기 때문에 max_y부터 min_y 까지로 범위를 설정해 주었다.
그리고 그 범위에 해당하는 y좌표에서 일치하는 교점이 있나 하나하나 살펴보아야 하기 때문에 step은 -1로 설정하였다.
별을 찍기 전에, 점을 먼저 찍어 초깃값 세팅을 하였다.
결과에서는 문자열 형태여야 하지만 중간에 별을 찍을 때 인덱싱으로 편하게 값을 바꾸기 위해 위해 dot이라는 리스트를 선언해 주었다.
초깃값은 '.' 요소가 min_x 이상 max_x 미만에 속하는 x값의 개수만큼 존재하는 것으로 정해 두었다.
그리고 별을 찍을 단계이다.
앞에서 sort_y는 y좌표 기준으로 오름차순 정렬되어 있으므로 sort_y의 맨 끝 요소부터 별이 찍히게 된다. (y값이 큰 것부터 출력되므로)
따라서 i와 sort[-1][1]이 일치하면 dot에서 x좌표 부분에 해당하는 인덱스 (sort_y[-1][0] - min_x = 해당 교점의 x좌표값 - 교점 통틀어서 가장 작은 x좌표값)의 값을 '*'로 치환해 준다.
이미 처리가 끝난 sort_y의 마지막 요소(교점)는 pop을 통해 제거해 주었다.
이렇게 한 줄 처리가 끝나면 answer에 dot 리스트를 공백 없이 합친 값을 추가해 준다.
같은 y좌표를 가지고 x좌표가 달라 한 줄에 별이 여러개 찍히는 경우도 있으므로 while문을 사용해 y좌표가 i값과 같은 교점일 때까지만 위와 같은 작업을 반복한다.
그리고 sort_y의 모든 교점을 처리하여 sort_y의 값이 비었을 경우에도 while문을 빠져나가야 한다.
반복문을 모두 빠져나와 마지막으로 answer를 return해주면 된다.
🗒️ 전체 코드
from itertools import combinations
def checkSlopeDifferent(line_1, line_2):
a, b, e = line_1
c, d, f = line_2
if a * d - b * c == 0:
return False
return True
def getIntVertex(line_1, line_2):
a, b, e = line_1
c, d, f = line_2
x = (b*f - e*d) / (a*d - b*c)
y = (e*c -a*f) / (a*d - b*c)
if x.is_integer() and y.is_integer():
return (int(x), int(y))
def solution(line):
answer = []
vertex = set()
for line_1, line_2 in combinations(line, 2):
if checkSlopeDifferent(line_1, line_2):
if getIntVertex(line_1, line_2) != None:
vertex.add(getIntVertex(line_1, line_2))
sort_x = sorted(list(vertex))
min_x = sort_x[0][0]
max_x = sort_x[-1][0]
sort_y = sorted(list(vertex), key = lambda x: x[1])
max_y = sort_y[-1][1]
min_y = sort_y[0][1]
for i in range(max_y, min_y-1, -1):
dot = ['.'] * (max_x - min_x + 1)
while True:
if len(sort_y) != 0:
if sort_y[-1][1] == i:
dot[sort_y[-1][0] - min_x] = '*'
sort_y.pop()
else:
break
else:
break
answer.append(''.join(dot))
return answer
🙂 느낀점
처음에 문제를 끝까지 읽지 않아 참고 사항에 공식이 있는 줄 모르고 더 복잡한 방법으로 교점을 구했었다.
앞으로는 문제를 침착하게 끝까지 읽어야겠다고 생각하였다.
참고사항의 공식을 사용하면 교점을 구하는 것까지는 어렵지 않게 풀 수 있었지만 별 찍기 코드를 작성하는 데에서 시간이 좀 걸렸다.
문제의 길이가 길고 그래프가 나와서 겁을 먹기 쉬운 문제였지만 차근차근 순서대로 생각하면 빠르게는 아니더라도 해결은 할 수 있는 문제였다.