알고리즘 풀이 - 프로그래머스(K번째 수(Lv 1), 정렬)

 

관련글

 

Quick 정렬 관련 포스팅은 여기를 참조
Stream 관련 포스팅은 추후 업데이트

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

현재 배열의 일부를 추출하여 정렬 후 해당 추출된 부분 중 주어진 index의 숫자 하나를 뽑아 전체를 배열로 만들어 반환하는 문제

 

 

2. 풀이

 

이 문제는 너무 간단한 문제라서 굳이 포스팅을 하지 않아도 되겠으나, 퀵 정렬의 직접 구현과 Stream 사용 연습을 하는 것을 고려하여 포스팅 한다.

 

정렬 관련 문제는 정렬 자체를 항상 직접 구현하는 연습을 하는 것이 좋다.

여기서는 정렬을 직접 구현하고, 숫자를 추출하는 것을 Stream을 통해서 하는 코드를 작성하여 풀었다.

 

구체적인 것은 코드를 아래에서 확인.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.util.List;
import java.util.ArrayList;
import java.util.stream.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        List<Integer> list = new ArrayList<>();
        
        for(int i=0; i < commands.length; i++){
            // command에서 주어진 인덱스 부분을 추출하여 배열로 생성하는 Stream
            int[] temp = IntStream
                    .range(commands[i][0]-1, commands[i][1])  // 범위 지정
                    .mapToObj(j -> array[j])                  // Object로 Mapping
                    .collect(Collectors.toList())             // Mapping된 내역을 List화
                    .stream()
                    .mapToInt(Integer::intValue)              // Object -> Int로 변경
                    .toArray();                               // 배열로 전환

            // Stream으로 sorted()를 쓰면 정렬되지만, 연습을 위해 직접 구현
            sort(temp, 0, temp.length-1);
            
            // 추출할 숫자를 뽑아 List에 추가
            list.add(temp[commands[i][2]-1]);
        }
        
        // List를 int 배열로 변환하여 반환
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    
    // Quick 정렬
    private void sort(int[] arr, int start, int end){
        int i = start;
        int j = end;
        int pv = arr[(start+end)/2];
        
        while(i<=j){
            while(arr[i] < pv) i++;
            while(arr[j] > pv) j--;
            if(i<=j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++; j--;
            }
        }
        if(start < j) sort(arr, start, j);
        if(i < end) sort(arr, i, end);
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.