99클럽 코테 스터디 6일차 TIL + Heap, PriorityQueue 우선순위 큐

✨ 문제 

K번째수

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번쨰까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

 

 

 

 

✨ 개념

PriorityQueue 우선순위 큐

- 우선순위 큐는 큐에 우선순위 개념을 적용한 것이다.

- 큐는 데이터가 들어온 순서대로 나가는 반면, 우선순위 큐는 데이터가 우선 순위를 가지며 우선순위가 높은 순서대로 나가게 된다.

- 우선순위 큐는 배열, 연결 리스트 등 여러 방법으로 구현 가능하지만 가장 효율적인 구조는 heap임.

- 우선순위 큐는 2가지로 나뉨.

최소 우선순위 큐 : 가장 우선 순위가 낮은 데이터 먼저 삭제

최대 우선순위 큐 : 가장 우선 순위가 높은 데이터 먼저 삭제

Heap 힙

- 힙은 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.

- 느슨한 정렬 상태를 유지함. (완전히 정렬된 상태는 아니지만 정렬이 안된 상태는 아님)

- 부모 노드의 키 값이 항상 자식 노드의 키 값보다 큼.

- 히프트리에서는 중복 값 허용

- 힙의 삽입, 삭제 연산 시간복잡도는 O(logN), 정렬 시간복잡도는 O(NlogN).

- 힙 정렬은 전체 자료 정렬보다는 가장 큰 값 몇 개만 필요할 때 최대로 유용하다.

 

 

 

✨ 최종코드

public static int[] solution(int[] array, int[][] commands) {
    List<Integer> list = new ArrayList<Integer>();

    for (int[] command : commands) {
        int startIdx = command[0] - 1;
        int endIdx = command[1];
        int targetIdx = command[2] - 1;

        int[] subArr = Arrays.copyOfRange(array, startIdx, endIdx);
        Arrays.sort(subArr);

        list.add(subArr[targetIdx]);
    }

    return list.stream().mapToInt(Integer::intValue).toArray();
}

 

forEach를 사용해 commands를 순회하며 배열의 시작, 끝, 타겟 인덱스 값을 변수에 넣어주었고, 해당 변수들을 copyOfRange 함수를 사용해 int 배열을 생성해주었다.

그리고 생성한 int 배열을 정렬한 뒤 정렬된 배열의 타겟 인덱스에 해당하는 값을 리스트에 추가해주었다.

commands 순회가 끝나면 list를 스트림을 사용해 int 배열로 변환한 뒤 리턴하도록 하였다.