K번째수

코딩테스트 연습 - K번째수 | 프로그래머스 스쿨

프로그래머스

 

💡접근방식

1. 배열을 i번째 ~ j번째 자르기
array의 i번째 숫자   ~   j번째 숫자
                 arr[i-1]   ~   arr[j-1]

2. 자른 배열을 정렬

3. 자른 배열에서 k위치에 있는 값 저장

💡알고리즘 설계

1. i~j번째에 해당하는 배열을 tempArray에 저장

2. Arrays.sort 메서드를 활용해 tempArray 정렬

3. tempArray에서 인덱스 [k-1]에 해당하는 원소값 answer 배열에 저장

💡시간복잡도

Arrays.sort 정렬

> n=100

입력의 크기가 아래와 같을 때:

• array.length = N ≤ 100
• commands.length = M ≤ 50

---

🧮 각 반복에서 수행되는 연산의 시간

1. 배열 슬라이스 및 복사
   • Arrays.copyOfRange(array, i-1, j) 은  O(N)
2. 정렬 연산
   • Arrays.sort(tempArray) 은 듀얼-피벗 퀵소트로 평균  O(Nlog⁡N)
3. K번째 요소 접근
   • 정렬된 배열에서 인덱스로 바로 가져오는 건 O(1)

---

✅ 전체 연산 반복 구조

이 과정을 총 M번 반복하므로:

T=M×(O(N)+O(Nlog⁡N))=O(M⋅Nlog⁡N)

 

이 입력 범위 N≤100, M≤50에서, 상수 값을 대입 => 약 35,000번

 

💡전체코드

import java.util.Arrays;	// copyOfRange, Arrays.toString() 메서드를 사용하기 위해 선언필요.
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int a=0;
        
        for(int[] arr : commands){
            int i = arr[0];
            int j = arr[1];
            int k = arr[2];
            
            int[] tempArray = Arrays.copyOfRange(array,i-1,j);	
            Arrays.sort(tempArray);
//          System.out.println(Arrays.toString(tempArray));
            
            answer[a] = tempArray[k-1];
            a++;
            
        }
        return answer;
    }
}