TIL (2024.06.20)

문제 1️⃣ (🔗 리트 코드 _ 최대도 최소도 아닌 값 찾기)

💡 IDEA : 배열 안 모든 값이 distinct 하다는 성질을 이용한다. 배열의 길이가 2 이하면 바로 -1 을 반환하고, 이 외의 경우 Arrays.sort 를 통해 배열을 정렬한 후 해당 배열의 인덱스 1 값을 반환한다.

import java.util.Arrays;

class Solution {
    public int findNonMinOrMax(int[] nums) {

        if (nums.length <= 2) return -1;

        Arrays.sort(nums);

        return nums[1];
    }
}

문제 2️⃣ (🔗 리트코드 _ Top 빈도수 k 개 구하기)

💡 IDEA : Num 클래스를 생성하여 Array.sort 를 통해 정렬된 nums 배열을 한번 돌면서 배열 속 숫자의 개수를 계산한다. 이때 동시에 PriorityQueue 에 Num 객체를 담는다. 이때 PriorityQueue 의 정렬 기준은 숫자 개수의 내림 차순이다. 이후 k 개 만큼 Queue 에서 poll 해서 정답 배열에 담아 반환한다.

import java.util.PriorityQueue;
import java.util.Arrays;

// Num 클래스 선언
class Num implements Comparable<Num> {
    int num;
    int cnt;
    
    // 생성자
    public Num (int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
    
    // PriorityQueue 정렬 기준
    public int compareTo (Num other) {
        return other.cnt - this.cnt;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
    	// (1) PriorityQueue 생성 및 nums 배열 속 숫자 세기
        PriorityQueue<Num> pq = new PriorityQueue<>();
        Arrays.sort(nums);

        int cnt = 1;

        for (int i=0; i<nums.length-1; i++) {
            if (nums[i] == nums[i+1]) {
                cnt++;
            }
            else {
                pq.add(new Num(nums[i], cnt));
                cnt = 1;
            }
        }

        if (cnt == 1) { // 마지막 값 담기
            pq.add(new Num(nums[nums.length-1], 1));
        }
        else {
            pq.add(new Num(nums[nums.length-1], cnt));
        }
        
        // (2) 개수 세기를 마친 후 PriorityQueue 에서 Top k 개를 빼낸 후 answer 배열에 담기
        int[] answer = new int[k];

        for (int i=0; i<k; i++) {
            answer[i] = pq.poll().num;
        }

        return answer;

    }
}
/*
조건
➡️ 가장 빈도가 높은 k 개의 숫자를 배열로 반환
➡️ 시간 복잡도가 O(n logn) 안쪽으로, n 은 nums 배열의 길이를 의미
*/

문제 3️⃣ (🔗 리트 코드 _ 그래프를 표현하기 위한 최소 선의 갯수)

💡 IDEA : 배열 정렬을 수행 한 후, 전 후 기울기 비교를 통해 선 추가 여부를 결정한다.

① 초기 IDEA

기울기 계산을 통한 기울기 비교 방식

➡️ 일반적으로 기울기 계산에 사용하는 (y2 - y1) / (x2 - x1) 을 double 자료형을 통해서 비교하면 정확한 비교가 될 수 있을 것이라고 생각했고, 해당 아이디어를 바탕으로 아래와 같이 비교 코드를 작성하였다.

while (!pq.isEmpty()) {
    now = next;
    next = pq.poll();

    double nowDir = (double) (now.price-next.price) / (now.day-next.day);

    if (preDir != nowDir) answer++;

    preDir = nowDir;
}

➡️ 그러나 이렇게 작성했을 때 double 또한 64bit 의 유한 비트수를 가지고 있기 때문에 비교될 값이 아주 작은 차이로 다르게 되면 반올림 과정에서 두 값이 동일한 특정값에 수렴하면서 정확한 측정이 어려워지고, 이로 인해 해당 테스트케이스에서는 오류가 발생하여 다른 결과값이 나오게 된다.

② 수정된 IDEA

비례 관계 확인을 통한 기울기 비교 방식

➡️ 이러한 문제를 해결하기 위해 기울기를 직접 구하는 방식이 아닌 비례 관계를 확인하는 방식으로 변경하였다. 해당 방식은 곱을 이용하는 방식으로 기존 방식처럼 반올림을 피할 수 있기 때문에 오차 범위가 확연히 줄어듬과 동시에 long 자료형을 사용하므로서 오버플로우를 방지하여 정확도를 더 높일 수 있다.

while (!pq.isEmpty()) {
    left = mid;
    mid = right;
    right = pq.poll();

    long dir_1 = (mid.price - left.price)*(right.day - mid.day);
    long dir_2 = (right.price -mid.price)*(mid.day - left.day);

    if (dir_1 != dir_2) answer++;

}

③ 개선 전 코드

import java.util.PriorityQueue;

class Chart implements Comparable<Chart> {
    int day;
    int price;

    public Chart (int day, int price) {
        this.day = day;
        this.price = price;
    }

    @Override
    public int compareTo (Chart other) {
        return this.day - other.day;
    }
}
class Solution {
    public int minimumLines(int[][] stockPrices) {
        if (stockPrices.length <= 2) {
            return stockPrices.length-1;
        }

        // (1) stockPrices 배열 정리
        PriorityQueue<Chart> pq = new PriorityQueue<>();

        for (int[] stock : stockPrices) {
            pq.add(new Chart(stock[0], stock[1]));
        }

        // (2) 차트 정리
        int answer = 1;

        Chart left = null;
        Chart mid = pq.poll();
        Chart right = pq.poll();

        while (!pq.isEmpty()) {
            left = mid;
            mid = right;
            right = pq.poll();

            long dir_1 = (mid.price - left.price)*(right.day - mid.day);
            long dir_2 = (right.price -mid.price)*(mid.day - left.day);

            if (dir_1 != dir_2) answer++;

        }

        return answer;
    }
}

➡️ day 기준으로 배열을 정렬하기 위해서 Char 클래스를 생성하고 PriorityQueue 를 사용하였는데 이렇게 할 경우 시간복잡도 및 공간복잡도가 높아지게 된다.

④ 개선 및 최종 코드

import java.util.Arrays;

class Solution {
    public int minimumLines(int[][] stockPrices) {
        if (stockPrices.length <= 2) return stockPrices.length-1;

        // (1) day 기준으로 정렬
        Arrays.sort(stockPrices,(o1,o2)-> o1[0]-o2[0]);

        // (2) 전체를 돌면서 기울기 비례 관계 확인
        int answer = 1;

        for (int i=0; i<stockPrices.length-2; i++) {
            int x1 = stockPrices[i][0];
            int x2 = stockPrices[i+1][0];
            int x3 = stockPrices[i+2][0];

            int y1 = stockPrices[i][1];
            int y2 = stockPrices[i+1][1];
            int y3 = stockPrices[i+2][1];

            long dir_1 = (y2-y1)*(x3-x2);
            long dir_2 = (y3-y2)*(x2-x1);

            if (dir_1 != dir_2) answer++;
        }

        // (3) 정답 반환
        return answer;
    }
}

➡️ Array.sort 과정에서 day 를 기준으로 정렬한다는 람다 표현식을 통해 sort 과정에서 필요한 Comparator 의 인터페이스를 생성하여 단계를 줄였다. Comparator 의 내부함수인 int compare(T o1, T o2) 를 람다식을 통해 표현했다고 할 수 있다.

// Comparator 메소드
int compare(T o1, T o2);

// 람다 표현 방식
Arrays.sort(stockPrices, (o1, o2) -> o1[0] - o2[0]);