프로그래머스 Level2 자바 - 교점에 별 만들기

2023. 6. 25. 12:02·알고리즘

문제

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

코드작성

해당 문제는 좌표를 표현해야 하므로 좌표를 나타내는 클래스를 우선 생성해 줍니다.

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

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

x,y 좌표는 데이터를 나타내 주므로 final을 이용해서 불변성을 갖게 하고, 해당 클래스는 생성자로 초기화 할 수있게 만들었습니다.

좌표 범위를 모르기 때문에, long을 이용해서 표현합니다.

1. 교점의 좌표 구하기

두 직선의 교점을 구하는 식

$$ a_{1}x + b_{1}y + c_{1} = 0 $$

$$ a_{2}x + b_{2}y + c_{2} = 0 $$

해당 직선의 교점은

다음과 같이 계산 할 수 있습니다

$$ x = \frac{(b_1c_2 - b_2c_1)}{(a_1b_2 - a_2b_1)} $$

$$ y = \frac{(a_2c_1 - a_1c_2)}{(a_1b_2 - a_2b_1)} $$

해당 식을 코드로 구현해 봅시다

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);
    };

반환된 정수 좌표를 List형태로 저장하는 코드를 solution에 작성해줍니다.

List<Point> points = new ArrayList<>();
        for(int i = 0; i < line.length; i++) {  // i번째 직선과 교차하는 점에서 정수만 탐색
            for(int j = i+1; j < line.length; j++){
                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의 최대, 최소값 구하기

별을 나타내기 위한 배열의 크기를 정하기 위해서 x와 y의 최대값과 최소값을 반환하는 함수를 선언합니다.

private Point getMinimumPoint(List<Point> points) { // 정수인 교점 x,y의 최소값 구하기 
        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){ // 정수인 교점 x,y의 최대값 구하기 
        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차원 배열 생성

구한 maximum값과 minimum 값을이용해서 solution 메서드에서 배열객체를 만들어 줍니다.

Point minimum = getMinimumPoint(points);  // 2차원 배열의 크기 결정
Point maximum = getMaximumPoint(points);
int width = (int) (maximum.x - minimum.x + 1);
int height = (int) (maximum.y - minimum.y + 1);

char[][] arr = new char[height][width]; //크기가 결정된 배열에 '.' 채워주기
    for(char[] row: arr){
        Arrays.fill(row, '.');
    };

4. 2차원 배열에 별 표시

일반 좌표와 달리 2차원 좌표는 음수(-) 좌표가 존재하지 않고, y축 좌표는 방향이 반대(아래로 내려 갈수록 값이 증가)입니다. 최대값과 최소값을 이용해서 좌표를 변환시켜 줍니다.

for (Point p : points){  //2차원 배열에는 -값 좌표가 없고, 0 부터 시작하는 값에서 최대값과 최소값과의 크기 차이를 이용해서 좌표를 결정해야 함
            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]);
        };

전체 코드

import java.util.*;

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

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

    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);
    };

    private Point getMinimumPoint(List<Point> points) { // 정수인 교점 x,y의 최소값 구하기
        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){ // 정수인 교점 x,y의 최대값 구하기
        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);
    }

    public String[] solution(int[][] line) {
        String[] answer = {};
        List<Point> points = new ArrayList<>();
        for(int i = 0; i < line.length; i++) {  // i번째 직선과 교차하는 점에서 정수만 탐색
            for(int j=i+1; j < line.length; j++){
                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);
                }
            };
        };
        Point minimum = getMinimumPoint(points);  // 2차원 배열의 크기 결정
        Point maximum = getMaximumPoint(points);
        int width = (int) (maximum.x - minimum.x + 1);
        int height = (int) (maximum.y - minimum.y + 1);

        char[][] arr = new char[height][width]; //크기가 결정된 배열에 '.' 채워주기
        for(char[] row: arr){
            Arrays.fill(row, '.');
        };

        for (Point p : points){  //2차원 배열에는 -값 좌표가 없고, 0 부터 시작하는 값에서 최대값과 최소값과의 크기 차이를 이용해서 좌표를 결정해야 함
            int x = (int) (p.x - minimum.x);
            int y = (int) (maximum.y - p.y);
            arr[y][x] = '*';
        };

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

        return answer = result;

    }
}
반응형
저작자표시 (새창열림)
'알고리즘' 카테고리의 다른 글
  • 프로그래머스 Level2 - 삼각달팽이
  • 유클리드 호제법 - 최대공약수 구하기 : 백준 13241번으로 알아보기
  • 11650번 - 좌표 정렬하기(Stream, Comparator 사용)
  • 백준 10978번 : 세로읽기 - 자바
LightSource
LightSource
어제보단 발전한 오늘의 나를 위한 블로그
    반응형
  • LightSource
    LightSourceCoder
    LightSource
  • 전체
    오늘
    어제
    • 분류 전체보기 (152)
      • Git (4)
      • Language (6)
        • Java (6)
      • Back-End (63)
        • Spring Boot (4)
        • MyBatis (1)
        • Oracle (1)
        • PL SQL (3)
        • JPA (26)
        • Spring Data JPA (5)
        • Spring MVC (8)
        • Spring (12)
        • Spring Security (2)
        • Redis (1)
      • Front-End (38)
        • 아이오닉 (2)
        • JSP (7)
        • JavaScript (4)
        • React (16)
        • TypeScript (3)
        • Angular (6)
      • AWS (1)
      • CI & CD (1)
      • 개발지식 (13)
        • 네트워크 (9)
        • CS 지식 (4)
      • 데이터모델링 (2)
      • Tool (1)
      • 프로젝트 (5)
      • 독후감 (2)
      • 잡생각 (0)
      • 면접 준비 (1)
      • 알고리즘 (14)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    react
    배열요소수정
    배요소열추가
    리액트
    배열요소삭제
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
LightSource
프로그래머스 Level2 자바 - 교점에 별 만들기
상단으로

티스토리툴바