[리트코드][JAVA] 2280. minimum-lines-to-represent-a-line-chart (라인 차트를 표현하기 위한 최소 라인)

💡 문제
minimum-lines-to-represent-a-line-chart (https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

• 정렬 알고리즘: 문제에서 주어진 데이터를 날짜별로 정렬하는 과정이 필요합니다. 따라서 정렬 알고리즘에 대한 이해와 구현능력이 필요합니다. 특히 시간 복잡도와 공간 복잡도를 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요합니다.
• 기하학적 관점에서의 문제 해결: 주식 가격 데이터를 직선으로 연결하는 문제는 기울기와 직선의 개념을 활용하여 해결됩니다. 따라서 기하학적 개념을 잘 이해하고 기울기를 계산하는 방법을 숙지해야 합니다.
• 동적 프로그래밍: 경우에 따라서는 주식 가격 변화 문제와 같이 연속적인 데이터를 처리할 때 동적 프로그래밍이 유용할 수 있습니다. 하지만 이 문제는 주로 기하학적 접근이 더 직관적이며 효과적입니다.
• 그래프 이론: 문제를 접근하는 다양한 방식 중 하나로, 주식 가격을 데이터 포인트 간의 연결로 생각하여 그래프로 표현하고, 최소한의 선(직선)으로 연결하는 문제로 해석할 수 있습니다. 따라서 그래프 이론의 기본 개념과 최소 신장 트리 등의 관련 알고리즘이 유용할 수 있습니다.
• 이산 수학: 주어진 데이터를 처리하고 분석하는 데 필요한 수학적 개념과 접근 방법을 이해하는 것이 중요합니다. 특히 수열과 관련된 문제를 푸는 데 유리할 수 있습니다.

정렬 알고리즘의 종류

정렬을 수행하는 다양한 알고리즘이 있으며, 각 알고리즘은 다른 방식으로 동작합니다. 주요 정렬 알고리즘에는 다음과 같은 것들이 있습니다:

• 버블 정렬(Bubble Sort): 인접한 두 원소를 비교하며 정렬하는 방식입니다. 간단하지만 비효율적인 경우가 많습니다.
• 삽입 정렬(Insertion Sort): 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 부분의 원소를 정렬된 부분에 삽입하는 방식입니다.
• 선택 정렬(Selection Sort): 배열에서 가장 작은(또는 큰) 원소를 선택하여 맨 앞(또는 맨 뒤)으로 옮기는 작업을 반복하는 방식입니다.
• 병합 정렬(Merge Sort): 분할 정복(divide and conquer) 방법을 이용하여 리스트를 반으로 나눈 후 정렬하고 다시 합치는 방식입니다. 재귀적으로 구현됩니다.
• 퀵 정렬(Quick Sort): 분할 정복 방법을 사용하며, 피벗(pivot)을 기준으로 리스트를 분할하고 각 부분을 정렬하는 방식입니다. 평균적으로 매우 빠른 속도를 가집니다.

---

🤓 문제 풀이

🔨 문제 설명

주어진 문제를 해결하기 위해서는 주어진 주식 가격을 나타내는 점들을 최소한의 직선으로 연결하는 방법을 찾아야 합니다. 이 문제는 기울기를 이용해 해결할 수 있습니다. 기울기가 일정하게 유지되는 구간을 하나의 직선으로 간주할 수 있기 때문입니다.

---

🔨 접근 방법

• 설명: "You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei."
  • 이 문장에서는 stockPrices 배열의 각 요소가 날짜 dayi와 가격 pricei를 나타내며, 이 정보를 이용하여 주식 가격의 변화를 분석할 수 있음을 암시합니다.
• 요구사항: "Return the minimum number of lines needed to represent the line chart."
  • 문제의 목적은 주어진 데이터 포인트를 연결하는 데 필요한 최소한의 직선(선) 개수를 구하는 것입니다. 즉, 주식 가격의 변화를 가장 효율적으로 표현할 수 있는 방법을 찾는 문제입니다.
• 예제 설명:
  • "Example 1: ... Explanation: The following 3 lines can be drawn to represent the line chart..."
  • 이 예시에서는 구체적인 데이터가 주어지고, 이를 몇 개의 직선으로 효율적으로 표현할 수 있는지에 대한 설명이 있습니다. 이를 통해 문제를 이해하고 구체적인 입력과 출력 예시를 확인할 수 있습니다.

---

🔨 문제 풀이 과정

• 입력 정렬: 먼저, dayi를 기준으로 오름차순으로 정렬합니다. 그래야 날짜 순서대로 점을 연결할 수 있습니다.
• 기울기 계산: 인접한 두 점의 기울기를 계산하여 이전 점과 현재 점 사이의 기울기를 비교합니다. 기울기가 달라지는 순간 새로운 직선이 필요합니다.
• 기울기 비교: 두 점 (x1, y1)와 (x2, y2)의 기울기는 (y2 - y1) / (x2 - x1)로 계산됩니다. 정수 나눗셈의 특성상, 기울기를 비교하기 위해 분모와 분자를 따로 비교해야 합니다.
• 기울기 변화 체크: 현재 기울기와 이전 기울기가 다를 때마다 직선의 수를 증가시킵니다.

---

🔨 정렬

문제를 해결하는 과정에서 직선의 개수를 최소화하는 것이 목표입니다. 이 문제는 기울기를 이용해 간단하게 해결할 수 있지만, 직선이 필요한 구간을 직접 계산하고 세는 방식도 가능합니다. 이러한 접근 방식은 보다 직관적이고 직접적인 구현을 통해 문제를 해결할 수 있습니다.

---

🔨 구현코드

import java.util.Arrays;

class Solution {
    public int minimumLines(int[][] stockPrices) {
        // 주어진 배열을 날짜(dayi) 기준으로 정렬
        Arrays.sort(stockPrices, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 최소 직선 개수 초기화
        int lines = 0;
        
        // 기울기 비교를 위한 이전 분자, 분모
        int prevDy = 0;
        int prevDx = 0;
        
        // 첫 번째 점부터 시작하여 기울기 변화 체크
        for (int i = 1; i < stockPrices.length; i++) {
            // 현재 점과 이전 점 사이의 기울기 계산
            int dy = stockPrices[i][1] - stockPrices[i - 1][1];
            int dx = stockPrices[i][0] - stockPrices[i - 1][0];
            
            // 첫 번째 기울기 또는 이전 기울기와 현재 기울기가 다른 경우
            if (i == 1 || dy * prevDx != dx * prevDy) {
                lines++;  // 새로운 직선이 필요
                prevDy = dy;
                prevDx = dx;
            }
        }
        
        return lines;
    }
}

---

📚 풀이 보완

코드 설명

• 정렬: Arrays.sort를 사용하여 주어진 stockPrices 배열을 dayi 기준으로 오름차순으로 정렬합니다.
• 변수 초기화: lines 변수를 0으로 초기화하여 최소 직선의 개수를 저장합니다. 그리고 prevDy와 prevDx를 초기화하여 이전 기울기를 저장합니다.
• 기울기 계산 및 비교:
  • 첫 번째 점과 두 번째 점 사이의 기울기를 계산합니다.
  • 두 번째 점 이후부터 이전 기울기와 현재 기울기를 비교하여 기울기가 달라지는 경우 lines를 증가시킵니다.
  • 기울기가 달라질 때마다 prevDy와 prevDx를 현재 기울기로 갱신합니다.
• 결과 반환: 계산된 lines 값을 반환하여 최소 직선의 개수를 출력합니다.

---

📍 Plus+

시간 복잡도

1. 정렬: Arrays.sort를 사용하여 stockPrices 배열을 날짜 기준으로 정렬하는 데 소요되는 시간 복잡도는 O(n log n)입니다. 여기서 n은 stockPrices 배열의 길이입니다.
2. 순회 및 기울기 계산: 정렬된 배열을 순회하면서 각 점과 이전 점 사이의 기울기를 계산하는 데 소요되는 시간 복잡도는 O(n)입니다. 여기서 n은 stockPrices 배열의 길이입니다.

따라서 전체 시간 복잡도는 O(n log n + n)이며, 이는 O(n log n)입니다. 정렬 과정이 주요 시간 소모 요소입니다.

 

공간 복잡도

추가적인 공간 사용: 이 코드는 추가적인 공간을 사용하지 않고, 상수 개의 변수만 사용하여 공간 복잡도는 O(1)입니다. 따라서 입력 데이터 외에 추가적인 메모리 사용이 없습니다.

요약

• 시간 복잡도: O(n log n) (정렬을 위한 시간 복잡도)
• 공간 복잡도: O(1) (추가적인 공간 사용 없음)