[프로그래머스] 10주차 위클리

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

코딩테스트 연습 - 10주차

 

문제

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

라고 했을 때, 각 직선의 교점을 *와 . 형태로 나타내기

 

제한사항

• 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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

내 풀이

-> 성공한 코드만 보려면 세번째 코드 확인

 

첫번째 - 69/100

class Solution {
    public static int maxX;
    public static int maxY;
    public static int minX;
    public static int minY;
    public static int[][] arr;
    
    public String[] solution(int[][] line) {
        maxX = -1000; maxY = -1000;
        minX = 1000; minY = 1000;
        Set<int[]> set = getCrossingSet(line);
        
        arr = new int[maxX-minX+1][maxY-minY+1];
        setArr(set);
        
        String[] answer = new String[arr[0].length];
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<arr[0].length;i++) {
            for (int j=0;j<arr.length;j++) {
                if(arr[j][i]==1) sb.append("*");
                else sb.append(".");
            }
            answer[i] = sb.toString();
            sb.setLength(0);
        }
        
        return answer;
    }
    
    public void setArr(Set<int[]> set) {
        for(int[] next: set) {
            next[0] = (next[0]>=0)?next[0]+Math.abs(minX):next[0]-minX;
            next[1] = maxY - next[1];
            arr[next[0]][next[1]] = 1;
        }
    }
    
    public Set<int[]> getCrossingSet (int[][] line) {
        Set<int[]> set = new HashSet<>();
        
        for(int i=0;i<line.length;i++) {
            for(int j=i+1;j<line.length;j++) {
                int[] line1 = line[i];
                int[] line2 = line[j];
                int ADBC = line1[0] * line2[1] - line1[1] * line2[0];
                if(ADBC != 0) {
                    float xf = (float) (line1[1] * line2[2] - line1[2] * line2[1])/ADBC;
                    float yf = (float) (line1[2] * line2[0] - line1[0] * line2[2])/ADBC;
                    
                    if(xf==Math.ceil(xf) && yf==Math.ceil(yf)) {
                    	int x = (int) xf;
                    	int y = (int) yf;
                    	
	                    set.add(new int[] {x, y});
	                    
	                    maxX = Math.max(x, maxX);
	                    maxY = Math.max(y, maxY);
	                    minX = Math.min(x, minX);
	                    minY = Math.min(y, minY);
                    }
                }
            }
        }
        return set;
    }
}

교점 찾기 -> 교점 돌며 배열 세팅 -> 배열 돌며 * 또는 . 체크하며 정답 배열 세팅

 

 

두번째 75.9/100

import java.util.*;

class Solution {
    public static int maxX = Integer.MIN_VALUE;
    public static int maxY = Integer.MIN_VALUE;
    public static int minX = Integer.MAX_VALUE;
    public static int minY = Integer.MAX_VALUE;
    public static String[] arr;
    
    public String[] solution(int[][] line) {
        Set<int[]> set = getCrossingSet(line);
        
        initialArr();
        setArr(set);
        
        return arr;
    }
    
    public void initialArr() {
		int arrLen = maxY-minY+1;
		arr = new String[arrLen];
        
		StringBuilder sb = new StringBuilder();
        for(int i=0;i<maxX-minX+1;i++) {
        	sb.append(".");
        }
        String str = sb.toString();
        for(int i=0;i<arrLen;i++) {
        	arr[i] = str;
        }
	}
    
	public void setArr(Set<int[]> set) {
        for(int[] next: set) {
            next[0] = (next[0]>=0)?next[0]+Math.abs(minX):next[0]-minX;
            next[1] = maxY - next[1];
            StringBuilder sb = new StringBuilder(arr[next[1]]);
            sb.setCharAt(next[0], '*');
            arr[next[1]] = sb.toString();
        }
    }
    
    public Set<int[]> getCrossingSet (int[][] line) {
        Set<int[]> set = new HashSet<>();
        int len = line.length;
        
        for(int i=0;i<len-1;i++) {
            for(int j=i+1;j<len;j++) {
                long ADBC = (long)line[i][0] * (long)line[j][1] - (long)line[i][1] * (long)line[j][0];
                if(ADBC == 0) { continue; }
                
                long numX = (long)line[i][1] * (long)line[j][2] - (long)line[i][2] * (long)line[j][1];
                long numY =(long)line[i][2] * (long)line[j][0] - (long)line[i][0] * (long)line[j][2];


                if(numX%ADBC != 0 || numY%ADBC != 0) { continue; }
                
            	int[] intArr = new int[] {(int) (numX/ADBC), (int) (numY/ADBC)};
                set.add(intArr);
                
                maxX = Math.max(intArr[0], maxX);
                maxY = Math.max(intArr[1], maxY);
                minX = Math.min(intArr[0], minX);
                minY = Math.min(intArr[1], minY);
            }
        }
        return set;
    }
}

변경 사항

• 교점 찾기 -> 배열 초기화 -> 교점 돌면서 *로 변경
• static 변수 초기화 방식
• 배열의 크기만큼 for문 돌 경우 매번 arr.length 구하지 않고 int 배열에 넣었다가 for문에서 사용
• int[][]를 거쳐 String[]으로 바꾸지 않고 바로 String[] 사용
• ADBC 구할때 int 아닌 long 사용

 

 

세번째 100/100

import java.util.*;

class Solution {
    public static int maxX = Integer.MIN_VALUE;
    public static int maxY = Integer.MIN_VALUE;
    public static int minX = Integer.MAX_VALUE;
    public static int minY = Integer.MAX_VALUE;
    public static String[] arr;
    
    public String[] solution(int[][] line) {
		Set<int[]> set = getCrossingSet(line);
        
        List<String> board = initialArr();
        setArr(set, board);
        
        String[] answer = new String[board.size()];
        for(int i=0; i<answer.length; i++) {
            answer[i] = board.get(i);
        }
        return answer;
    }
    
    public List<String> initialArr() {
        StringBuilder sb = new StringBuilder();
        for(int j=minX; j<=maxX; j++) {
            sb.append(".");
        }
        String str = sb.toString();
        
        List<String> board = new ArrayList<>();
        for(int i=minY; i<=maxY; i++) {
            board.add(str);
        }
        return board;
	}
    
	public List<String> setArr(Set<int[]> set, List<String> board) {
        for(int[] s: set) {
        	StringBuilder sb = new StringBuilder(board.get(Math.abs(s[1] - maxY)));
            sb.setCharAt(Math.abs(s[0] - minX), '*');
            board.set(Math.abs(s[1] - maxY), sb.toString());
        }
        return board;
    }
    
    public Set<int[]> getCrossingSet (int[][] line) {
        Set<int[]> set = new HashSet<>();
        int len = line.length;
        
        for(int i=0;i<len-1;i++) {
            for(int j=i+1;j<len;j++) {
                long a,b,c,d,e,f;
                a = line[i][0]; b = line[i][1]; e = line[i][2];
                c = line[j][0]; d = line[j][1]; f = line[j][2];
                
                long ADBC = a * d - b * c;
                if(ADBC == 0) { continue; }
                
                long numX = b*f - e*d;
                long numY = e*c - a*f;

                if(numX%ADBC != 0 || numY%ADBC != 0) { continue; }
                
            	int[] intArr = new int[] {(int) (numX/ADBC), (int) (numY/ADBC)};
                set.add(intArr);
                
                maxX = Math.max(intArr[0], maxX);
                maxY = Math.max(intArr[1], maxY);
                minX = Math.min(intArr[0], minX);
                minY = Math.min(intArr[1], minY);
            }
        }
        return set;
    }
}

바뀐 점

• answer 배열의 크기를 미리 계산하는게 헷갈려서 List 이용
• 범위를 0 ... max값+min값+1이 아니라 min값 ... max 값으로 잡음
• 가독성을 위해 (long) line[i][j] 형식을 long형 변수에 담음