Programmers - 교점에 별 만들기 with JAVA

 

 

 

로직 및 고찰

우선 아이디어는 선마다 교점을 구하고 그것을 그래프로 표현했다.

선의 수는 최대 1000개로 약 50만회? 정도면 모두 구할 수 있기에 아이디어의 시간복잡도는 충분하다.

 

나는 아래의 두가지 오류가 발생했었다.

 

메모리 초과 오류 

- Double.MAX_VALUE, MIN_VALUE로 처리시 모든 좌표들에 대해 원활환 처리가 되지 않았다. 따라서 그냥 첫번째 인덱스를 기준으로 처리하는게 깔끔한 것 같다.

 

범위 초과

- A,B,C의 범위는 10만 이하이다. 따라서 A*B시에 백억?까지 범위가 올라갈 수 있다. 따라서 long 변수에 더하고 곱하던가 모든 int를 long으로 처리 후 계산을 해야 범위가 초과되지 않는다.

 

 

 

 

코드

import java.util.*;
class Solution {
    // 문제 - 자료형(공식 long처리), 메모리(max, min 변수들), 시간 복잡도
    public List<String> solution(int[][] line) {
        List<List<Double>> result = new ArrayList<>();
        for(int i=0; i<line.length; i++){
            int[] l1 = line[i];
            for(int j=i+1; j<line.length; j++){
                int[] l2 = line[j];
                double bottom = ((long)l1[0]*(long)l2[1]
                                 -(long)l1[1]*(long)l2[0]);
                if(bottom == 0.0){
                    continue;
                }
                double x = ((long)l1[1]*(long)l2[2]
                            -(long)l1[2]*(long)l2[1])/bottom;
                double y = ((long)l1[2]*(long)l2[0]
                            -(long)l1[0]*(long)l2[2])/bottom;
                if(x == -0.0){
                    x = 0.0;
                }
                if(x != (double)(long)x | y != (double)(long)y){
                    continue;
                }
                result.add(Arrays.asList(x, y));
            }
        }
        List<String> answer = new ArrayList<>();
        if(result.size() == 1){
            answer.add("*");
            return answer;
        }
        double x_min = result.get(0).get(0);
        double x_max = result.get(0).get(0);
        double y_min = result.get(0).get(1);
        double y_max = result.get(0).get(1);
        for(int i=1; i<result.size(); i++){
            double x = result.get(i).get(0);
            double y = result.get(i).get(1);
            x_min = Math.min(x, x_min);
            x_max = Math.max(x, x_max);
            y_min = Math.min(y, y_min);
            y_max = Math.max(y, y_max);
        }
        for(double y=y_max; y>=y_min; y--){
            StringBuilder sb = new StringBuilder();
            for(double x=x_min; x<=x_max; x++){
                if(result.contains(Arrays.asList(x, y))){
                    sb.append("*");
                }
                else{
                    sb.append(".");
                }
            }
            answer.add(sb.toString());
        }
        return answer;
    }
}

 

import java.util.*;
class Solution {
    public List<String> solution(int[][] line) {
        List<String> answer = new ArrayList<>();
        List<List<Long>> check = new ArrayList<>();
        for(int i=0; i<line.length; i++){
            int[] line1 = line[i]; 
            for(int j=i+1; j<line.length; j++){
                int[] line2 = line[j];
                double adbc = line1[0]*line2[1] - line1[1]*line2[0];
                if(adbc == 0){
                    continue;
                }
                double x = ((long)line1[1]*(long)line2[2]
                            -(long)line1[2]*(long)line2[1])/adbc;
                double y = ((long)line1[2]*(long)line2[0]
                            -(long)line1[0]*(long)line2[2])/adbc;
                if(x == -0.0){
                    x = 0.0;
                }
                if(x != (double)(long)x){
                    continue;
                }
                if(y != (double)(long)y){
                    continue;
                }
                check.add(Arrays.asList((long)x, (long)y));
            }
        }
        if(check.size() == 1){
            answer.add("*");
            return answer;
        }
        long x_min = check.get(0).get(0);
        long x_max = check.get(0).get(0);
        long y_min = check.get(0).get(1);
        long y_max = check.get(0).get(1);
        for(List<Long> now : check){
            x_min = Math.min(x_min, now.get(0));
            x_max = Math.max(x_max, now.get(0));
            y_min = Math.min(y_min, now.get(1));
            y_max = Math.max(y_max, now.get(1));
        }
        for(long y=y_max; y>=y_min; y--){
            StringBuilder sb = new StringBuilder();
            for(long x=x_min; x<=x_max; x++){
                if(check.contains(Arrays.asList(x, y))){
                    sb.append("*");
                }
                else{
                    sb.append(".");
                }
            }
            answer.add(sb.toString());
        }
        return answer;
    }
}