[프로그래머스] 교점에 별 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/87377?language=java

프로그래머스

---

1. 아이디어

이 문제에서는 직선들이 주어지고, 주어진 직선들의 교점 중 좌표 값이 정수인 좌표들을 2차원 배열에 표현해야 한다.

 

<문제 풀이 흐름>

1. 모든 직선 쌍에 대해 반복

    A. 교점 좌표 구하기

    B. 정수 좌표만 저장

2. 저장된 정수들에 대해 x, y 좌표의 최댓값 최솟값 구하기

3. 구한 최댓값, 최솟값을 이용하여 2차원 배열의 크기 결정

4. 2차원 배열에 별 표시

5. 문자열 배열로 변환 후 반환

 

2. 코드 작성

- Point 클래스

private static class Point {
    public final long x, y;

    private Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
}

좌표를 표현해야 하니 좌표를 나타내는 클래스 생성

 

1. 모든 직선 쌍에 대해 반복

for(int i=0; i<line.length; i++) {
    for(int j=i+1; j<line.length; j++) {
        . . .
    }
}

 

1-A. 교점 좌표 구하기

private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2) {
    // 교점 구해서 반환하기
    double x = (double) (b1*c2 - b2*c1) / (a1*b2 - a2*b1);
    double y = (double) (a2*c1 - a1*c2) / (a1*b2 - a2*b1);

    if(x%1 != 0 || y%1 != 0) return null;

    return new Point((long) x, (long) y);
}

 

1-B. 정수 좌표만 저장

List<Point> points = new ArrayList<>();
for(int i=0; i<line.length; i++) {
    for(int j=i+1; j<line.length; j++) {
        // line[i], line[j]를 이용하여 1-A, 1-B 수행
        Point intersection = intersection(line[i][0], line[i][1], line[i][2],
                                          line[j][0], line[j][1], line[j][2]);
        if(intersection != null) {
            points.add(intersection);
        }
    }
}

 

 

2. 저장된 정수들에 대해 x, y 좌표의 최댓값, 최솟값 구하기

- getMinimumPoint, getMaximumPoint()

private Point getMinimumPoint(List<Point> points) {
    // 가장 작은 좌표 찾기
    long x = Long.MAX_VALUE;
    long y = Long.MAX_VALUE;

    for(Point p : points) {
        if(p.x < x) x = p.x;
        if(p.y < y) y = p.y;
    }

    return new Point(x,y);
}

private Point getMaximumPoint(List<Point> points) {
    // 가장 큰 좌표 찾기
    long x = Long.MIN_VALUE;
    long y = Long.MIN_VALUE;

    for(Point p : points) {
        if(p.x > x) x = p.x;
        if(p.y > y) y = p.y;
    }

    return new Point(x,y);
}

 

3. 구한 최댓값, 최솟값을 이용하여 2차원 배열 크기 결정

Point minimum = getMinimumPoint(points);
Point maximum = getMaximumPoint(points);

int width = (int) (maximum.x - minimum.x + 1);
int height = (int) (maximum.y - minimum.y + 1);

 

4. 2차원 배열에 별 표시

for(Point p : points) {
    // 2차원 배열에 별 찍기
    int x = (int) (p.x - minimum.x);
    int y = (int) (maximum.y - p.y);
    arr[y][x] = '*';
}

 

5. 문자열 배열로 변환 후 반환

String[] result = new String[arr.length];
for(int i=0; i<result.length; i++) {
    result[i] = new String(arr[i]);
}
return result;

 

결론

문제를 효율적으로 해결하는 능력을 기르자. 문제의 전체적인 풀이 흐름을 구상하고, 그에 맞게 코드를 하나씩 차근차근 작성할 것