(2024-11-28) TIL

 

1.데일리 루틴(SQL)

 

SELECT
    USER_ID, PRODUCT_ID
FROM
    ONLINE_SALE
GROUP BY
    USER_ID, PRODUCT_ID
HAVING
    count(SALES_DATE) > 1
ORDER BY
    USER_ID,
    PRODUCT_ID DESC

 

 

 

2.데일리 루틴(Java)

 

import java.util.LinkedList;

class Solution {
    public static int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        LinkedList<Integer> honors = new LinkedList<>();


        for (int i = 0; i < score.length; i++) {
            int number = score[i];
            if (i == 0) {
                honors.add(number);
                answer[i] = number;
                continue;
            }

            if (i < k) {
                insert(honors, answer, number, i);
                answer[i] = honors.getLast();
                continue;
            }

            insert(honors, answer, number, i);
            honors.removeLast();
            answer[i] = honors.getLast();

        }


        return answer;
    }


    public static void insert(LinkedList<Integer> honors, int[] answer, int number, int i) {
        for (int j = 0; j < honors.size(); j++) {
            if (number >= honors.get(j)) {
                honors.add(j, number);
                return;
            }
        }
        honors.add(number);
    }
}

 

문제 설명

주어진 문제는 성적 배열 score에서 상위 k개의 성적을 기반으로 새로운 배열 answer를 생성하는 것이다. 각 인덱스 i에 대해 answer[i]는 인덱스 i까지의 성적 중 최대 k개의 성적 중 가장 낮은 성적을 나타내야 한다.

성능 분석

• 이 알고리즘은 각 성적을 honors에 삽입하는 과정에서 최악의 경우 O(n) 복잡도를 가지므로, 전체 시간 복잡도는 O(n^2)이다. 그러나 k가 작고 성적의 개수가 많을 때도 효율적으로 작동한다.

개선 방향

• 우선순위 큐의 경우 삽입의 시간복잡도가 O(logN)이다. 기존과 결합하면 O(nlogN)이 될 것이다. 자료 규모가 큰 경우 해당 방식을 택하는 게 낫겠다. 실제로 다른 이들의 풀이도 상위권은 우선순위 큐를 채택하였다.

링크드리스트를 쓴 경우. 극단적 경우에 속도가 느리다.

우선순위 큐를 쓴 경우. 안정적 속도를 보장한다.

 

 

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스