프로그래머스 - 교점에 별 만들기(87377)

문제 설명 및 제한사항은 너무 길어서 생략. 아래 링크 참조
https://school.programmers.co.kr/learn/courses/30/lessons/87377

프로그래머스

 

접근 방식 1

1. 아래 식을 참고해서 교점을 구해 교점을 집합에 넣는다(중복 제거를 위해 집합 사용)

2. 분모가 0일 경우 예외처리를 해준다.

3. x축의 길이와 y축의 길이를 구해 2중 for문의 범위를 정한다.

4. 2중 for문을 돌면서 (i, j)가 교점인 경우 *을 찍고 아니면 .을 찍는다.

5. answer에 append한 후 반환한다.

 

풀이 코드 1(오답)

def solution(line):
    answer = []
    
    meets = set() # 교점을 저장할 집합
    
    for i in range(len(line)-1): # 식 2개를 비교해야하기 때문에 range는 len(line)-1
        for j in range(i+1, len(line)): # i+1부터 마지막 식까지 비교
	        # 기준이 되는 식
            x1 = line[i][0] 
            y1 = line[i][1]
            num1 = line[i][2]
            
    		# 비교할 식        
            x2 = line[j][0]
            y2 = line[j][1]
            num2 = line[j][2]
            
            # 분모
            denom = ((x1*y2) - (y1*x2))
            
            # x, y의 분자
            mole_x = ((y1*num2) - (num1*y2))
            mole_y = ((num1*x2) - (x1*num2))
            
            # 분모가 0인 경우 예외처리
            if denom == 0:
                continue
                
            # 새로운 x, y 좌표
            nx = mole_x / denom
            ny = mole_y / denom
            
            # 새로운 x, y 좌표가 정수일 경우만 교점으로 간주
            if nx == int(nx) and ny == int(ny):
                meets.add((int(nx), int(ny)))
                
    
    # x축의 최소값과 최대값을 구해서 길이 산정
    min_x = min(meet[0] for meet in meets)
    max_x = max(meet[0] for meet in meets)
    len_x = abs(max_x - min_x) + 1
    
    # y축의 최소값과 최대값을 구해서 길이 산정
    
    min_y = min(meet[1] for meet in meets)
    max_y = max(meet[1] for meet in meets)
    len_y = abs(max_y - min_y) + 1
    
    for i in range(len_y):
        tmp = ""
        for j in range(len_x):
            if (j, i) in meets:
                tmp += "*"
            else:
                tmp += "."
        answer.append(tmp)
    
    return answer

 

틀린 이유

범위를 abs()함수를 이용햇는데 좌표 평면은 0부터 시작하지 않는다, abs를 사용하지 않고 min과 max를 그대로 사용해야함

 

풀이 코드2(오답)

def solution(line):
    answer = []
    meets = set()
    
    for i in range(len(line)-1):
        x1 = line[i][0]
        y1 = line[i][1]
        num1 = line[i][2]
        
        for j in range(i+1, len(line)):
            x2 = line[j][0]
            y2 = line[j][1]
            num2 = line[j][2]
            
            denom = ((x1*y2) - (y1*x2))
            mole_x = ((y1*num2) - (num1*y2))
            mole_y = ((num1*x2) - (x1*num2))
            
            if denom == 0:
                continue
            nx = mole_x / denom
            ny = mole_y / denom
            if nx == int(nx) and ny == int(ny):
                meets.add((int(nx), int(ny)))
                
    
    min_x = min(meet[0] for meet in meets)
    max_x = max(meet[0] for meet in meets)
    
    min_y = min(meet[1] for meet in meets)
    max_y = max(meet[1] for meet in meets)
    
    for i in range(max_y, min_y-1, -1):
        tmp = ""
        for j in range(max_x, min_x-1, -1):
            if (j, i) in meets:
                tmp += "*"
            else:
                tmp += "."
        answer.append(tmp)

    return answer

 

수정 사항 및 틀린 이유

- 기준이 되는 x1, y1, num1을 바깥 쪽 for으로 뺏다.(기준이 되는 x,y,상수는 변하지 않기 때문)

- *을 찍는 for문을 x, y의 길이가 아닌, max, min값을 그대로 사용했다.

-> 좌표평면을 왼쪽 위부터 생각해보면 y는 최대값, x는 최소값부터 시작해서 y는 아래로 갈수록 줄어들고, x는 오른쪽으로 갈수록 커진다.

 

풀이 코드3(정답)

def solution(line):
    answer = []
    meets = set()
    for i in range(len(line)-1):
        x1 = line[i][0]
        y1 = line[i][1]
        num1 = line[i][2]
        
        for j in range(i+1, len(line)):
            x2 = line[j][0]
            y2 = line[j][1]
            num2 = line[j][2]
            
            denom = ((x1*y2) - (y1*x2))
            mole_x = ((y1*num2) - (num1*y2))
            mole_y = ((num1*x2) - (x1*num2))
            
            if denom == 0:
                continue
            nx = mole_x / denom
            ny = mole_y / denom
            if nx == int(nx) and ny == int(ny):
                meets.add((int(nx), int(ny)))
                
    
    min_x = min(meet[0] for meet in meets)
    max_x = max(meet[0] for meet in meets)
    
    min_y = min(meet[1] for meet in meets)
    max_y = max(meet[1] for meet in meets)
    
    for i in range(max_y, min_y-1, -1):
        tmp = ""
        for j in range(min_x, max_x+1):
            if (j, i) in meets:
                tmp += "*"
            else:
                tmp += "."
        answer.append(tmp)

    return answer

 

주의 사항

좌표평면이 등장할 경우 각 사분면의 x,y값의 증감을 잘 생각하자.