CODEKATA 138 ~ 139

138번 교점에 별 만들기

/*
문제 분석
1. 정보
    - Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표의 별을 그리려 함

2. 목표
    - 직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어질 때, 모든 별을 포함하는 최소 사각형을 return
3. 제약 조건
    - line의 세로 행 길이는 2 이상 1000 이하
        - line의 가로 길이는 3
        - 각 원소는 A, B, C 형태
        - A, B, C는 -100000 이상 100000 이하 정수
        - 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않음
        - A = 0 이면서 B = 0인 경우는 주어지지 않음
    - 정답은 1000 * 1000 크기 이내에서 표현됨
    - 별이 한개 이상 그려지는 입력만 주어짐


풀이
1. 아이디어
    - 직선의 개수는 2 이상 1000 이하
        - 두 직선의 교점을 모든 직선에 대하여 구함
            - 교점 x : (line[i][1] * line[j][2] - line[i][2] * line[j][1]) / (line[i][0] * line[j][1] - line[i][1] * line[j][0])
            - 교점 y : (line[i][2] * line[j][0] - line[i][0] * line[j][2]) / (line[i][0] * line[j][1] - line[i][1] * line[j][0])
            - 위 교점을 double 값으로 구한뒤, long으로 캐스팅하여 정수인지 확인
            - 정수 값이라면, HashSet<Point>에 추가
            - minX, maxX, minY, maxY 값 업데이트
    - 모든 직선에 대하여 정수 교점을 구하였다면
        - 격자판 생성
             - X : maxX - minX + 1
             - Y : maxY - minY + 1
        - 모든 칸을 .로 초기화 한뒤 set에서 하나씩 뽑아 *로 변환
            - 위치는 (x - minX, maxY - y)
        - 변환 완료 후 결과값 형식에 맞게 return
*/

import java.util.Arrays;
import java.util.HashSet;

class Solution {

        class Point {
            long x;
            long y;

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

        HashSet<Point> points = new HashSet<>();
        long minX = Long.MAX_VALUE, minY = Long.MAX_VALUE;
        long maxX = Long.MIN_VALUE, maxY = Long.MIN_VALUE;

        public String[] solution(int[][] line) {
            for (int i = 0; i < line.length - 1; i++) {
                for (int j = i + 1; j < line.length; j++) {
                    long under = (long) line[i][0] * line[j][1] - (long) line[j][0] * line[i][1];
                    if (under == 0) {
                        continue;
                    }

                    long upX = (long) line[i][1] * line[j][2] - (long) line[j][1] * line[i][2];
                    long upY = (long) line[i][2] * line[j][0] - (long) line[j][2] * line[i][0];

                    if (upX % under == 0 && upY % under == 0) {
                        long x = upX / under;
                        long y = upY / under;
                        points.add(new Point(x, y));

                        minX = Math.min(minX, x);
                        minY = Math.min(minY, y);
                        maxX = Math.max(maxX, x);
                        maxY = Math.max(maxY, y);
                    }
                }
            }
            int width = (int)(maxX - minX + 1);
            int height = (int)(maxY - minY + 1);

            char[][] grid = new char[height][width];

            for (char[] row : grid) {
                Arrays.fill(row,'.');
            }
            
            for (Point p : points) {
                int row = (int)(maxY - p.y);
                int col = (int)(p.x - minX);
                grid[row][col] = '*';
            }

            String[] answer = new String[height];
            for (int i = 0; i < height; i++) {
                answer[i] = new String(grid[i]);
            }

            return answer;
        }
    }

139번 택배 배달과 수거하기

/*
문제 분석
1. 정보
    - 일렬로 나열된 n개의 집에 택배를 배달하려 함.
    - 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하고, 배달을 다니며 빈 재활용 택배 상자들을 수거하려 함
    - 배달할 택배들은 모두 재활용 택배 상자에 담겨 물류창고에 보관되어 있음
    - i번째 집은 물류창고에서 거리 i만큼 떨어져 있음
    - i번째 집은 j번째 집과 j - i 거리만큼 떨어져 있음
    - 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있음
    - 배달할 재활용 택배 상자들을 실어 물류 창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배상자들을 수거해 물류창고에 내림
    - 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류 창고까지 돌아올 수 있는 최소 이동 거리를 구하려 함
    - 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거 가능
2. 목표
    - 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어짐
    - 이때 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return

3. 제약 조건
    - 1 ≤ cap ≤ 50
    - 1 ≤ n ≤ 100,000
    - deliveries의 길이 = pickups의 길이 = n
        - deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수
        - pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수
        - 0 ≤ deliveries의 원소 ≤ 50
        - 0 ≤ pickups의 원소 ≤ 50
    - 트럭의 초기 위치는 물류창고

풀이
1. 아이디어
    - 가장 먼곳 부터 차례대로 배달 및 수거
        - 이때, cap에 허용되는 범위만큼 배달을 하고, cap에 허용되는 범위만큼 상자를 가져오도록 함
    - deliveries[]에서 cap 허용범위 만큼 택배를 쌓음
        - deliveries를 업데이트 및 가장 먼곳의 거리를 저장
    - pickups에서 cap 허용범위 만큼 택배를 쌓음
        - pickups를 업데이트 및 가장 먼곳의 거리를 저장
    - 두 거리중 더 긴 거리 X 2를 종합 거리에 추가
    - 해당 메서드를 deliveries와 pickup의 모든 택배가 없어질 때 까지 진행
*/

class Solution {

        long answer = 0;

        public long solution(int cap, int n, int[] deliveries, int[] pickups) {
            int dIdx = n - 1;
            int pIdx = n - 1;

            while (dIdx >= 0 || pIdx >= 0) {
                int maxDist = 0;

                int remainCap = cap;

                while (dIdx >= 0 && remainCap > 0) {
                    if (deliveries[dIdx] > 0) {
                        int deliver = Math.min(remainCap, deliveries[dIdx]);
                        deliveries[dIdx] -= deliver;
                        remainCap -= deliver;
                        maxDist = Math.max(maxDist, dIdx + 1);
                    }

                    while(deliveries[dIdx] == 0) {
                        dIdx--;
                        if (dIdx < 0) {
                            break;
                        }
                    }
                }

                remainCap = cap;

                while (pIdx >= 0 && remainCap > 0) {
                    if (pickups[pIdx] > 0) {
                        int pickup = Math.min(remainCap, pickups[pIdx]);
                        pickups[pIdx] -= pickup;
                        remainCap -= pickup;
                        maxDist = Math.max(maxDist, pIdx + 1);
                    }

                    while (pickups[pIdx] == 0) {
                        pIdx--;
                        if (pIdx < 0) {
                            break;
                        }
                    }
                }

                if (maxDist > 0) {
                    answer += maxDist * 2L;
                }
            }

            return answer;
        }
    }