2023-06-20 TIL (Spring, 알고리즘 문풀)

오늘 학습한 내용

• Spring (Spring Security, Validation)
• 알고리즘 문풀

---

문제상황

오늘 문제를 겪고 해결까지 했던 문제는 

 

'교점에 별 만들기'이다.

프로그래머스 Lv.2에 있는 문제기 때문에 매우 어려웠고 여러번의 실패를 겪었다.

 

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

프로그래머스

---

시도한 내용

우선 다음과 같이 문제 풀이를 구상하는데 긴 시간을 투자했다. 구상은 노트에 끄적이면서 했다.

문제 구상

구상했던 내용은 다음과 같다.

• 이중 for문을 사용하여 각 교점들의 좌표를 구한다.

for(int i=0; i<line.length-1; i++) {
            for(int j=i; j<line.length; j++) {
                if(!Arrays.equals(operate(line[i], line[j]), defaultArr)) {
                    long[] intArr = operate(line[i], line[j]);
                    list.add(new Coordinate(intArr[0], intArr[1]));
                }
            }
        }

• 교점들의 좌표를 담을 수 있는 리스트를 만들기 위해 좌표를 저장하는 클래스를 만든다.

// 좌표를 담는 객체를 위한 클래스
class Coordinate {
    private long x;
    private long y;

    public Coordinate(long x, long y) {
        this.x = x;
        this.y = y;
    }

    public long getX() {
        return x;
    }

    public long getY() {
        return y;
    }

• 리스트를 생성한 뒤 각각의 좌표를 담는다.
• 그 후 새로운 배열을 만들어서 모든 원소에 .을 찍고, 리스트에 속한 좌표만 *을 찍는다.
• 각 row를 join을 사용하여 문자열로 바꾼 뒤 return한다.

---

문제를 해결하면서 겪었던 문제들을 나열하면

• 주어진 배열의 원소를 계산할 때 int의 범위를 넘어갈 수 있다. ( Integer Overflow 발생)
• 배열의 길이는 int형만 가능하다.

---

해결

해결한 코드는 다음과 같다.

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        long[] defaultArr = {1001, 1001};

        List<Coordinate> list = new ArrayList<>();

        for(int i=0; i<line.length-1; i++) {
            for(int j=i; j<line.length; j++) {
                if(!Arrays.equals(operate(line[i], line[j]), defaultArr)) {
                    long[] intArr = operate(line[i], line[j]);
                    list.add(new Coordinate(intArr[0], intArr[1]));
                }
            }
        }

        //최댓값 구하기
        long xMax = list.get(0).getX(), yMax = list.get(0).getY();

        for(int i=0; i<list.size(); i++) {
            if(xMax<list.get(i).getX()) {
                xMax = list.get(i).getX();
            }
            if(yMax<list.get(i).getY()) {
                yMax = list.get(i).getY();
            }
        }

        //최솟값 구하기
        long xMin = list.get(0).getX(), yMin = list.get(0).getY();

        for(int i=0; i<list.size(); i++) {
            if(xMin > list.get(i).getX()) {
                xMin = list.get(i).getX();
            }
            if(yMin > list.get(i).getY()) {
                yMin = list.get(i).getY();
            }
        }

        //맞는 배열의 크기를 구하고
        String[][] answer = new String[(int)(yMax-yMin)+1][(int)(xMax-xMin)+1];
        for (String[] strings : answer) {
            Arrays.fill(strings, ".");
        }

        // 교점이 있는 부분만 *로 바꾼다.
        long a = -yMin;
        long b = -xMin;

        for (Coordinate coordinate : list) {
            answer[(int)(coordinate.getY() + a)][(int)(coordinate.getX() + b)] = "*";
        }

        String[] answerArr = new String[answer.length];
        for (int i = 0; i < answerArr.length; i++) {
            answerArr[i] = String.join("",answer[i]);
        }

        String[] realAnswer = new String[answerArr.length];
        for(int i = 0; i < realAnswer.length; i++) {
            realAnswer[i] = answerArr[answerArr.length-1-i];
        }
        
        // System.out.println(Arrays.toString(realAnswer));
        return realAnswer;


    }

    // 교점을 계산하는 메소드
    private static long[] operate(int[] arr, int[] arr2) {
        long[] result = {1001, 1001};

        long a = (long)arr[1]*(long)arr2[2] - (long)arr[2]*(long)arr2[1]; //BF-ED
        long b = (long)arr[2]*(long)arr2[0] - (long)arr[0]*(long)arr2[2]; //EC-AF
        long c = (long)arr[0]*(long)arr2[1] - (long)arr[1]*(long)arr2[0]; //AD-BC

        if( c != 0 && a % c == 0 && b % c == 0 ) {
            result[0] = (a / c);
            result[1] = (b / c);
            return result;
        }

        return result;
    }
}

// 좌표를 담는 객체를 위한 클래스
class Coordinate {
    private long x;
    private long y;

    public Coordinate(long x, long y) {
        this.x = x;
        this.y = y;
    }

    public long getX() {
        return x;
    }

    public long getY() {
        return y;
    }
}

---

알게된 내용

• 알고리즘 문제를 해결할 때는 항상 Overflow를 조심하자.
• 배열의 길이를 나타낼때는 int만 사용하자.
• 기본적인 형식을 담는 것이 생각나지 않을 때에는 객체를 생성하는 방향도 고려해보자.

---