[프로그래머스] K번째수 for JAVA

 

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

코딩테스트 연습 - K번째수

 

 

 

문제

 

 

 

---

 

내가 푼 방법

 

 

그냥 문제를 정리하고 풀라는대로 풀었다. for문으로 2차원 배열인 commands의 0~n번째 행을 읽고...했다.

 

 

 

 

코드

 

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length]; // 초기화 해줘야 index 에러가 안뜬다
        
        for(int i = 0; i < commands.length; i++){ // 행
             ArrayList<Integer> cal = new ArrayList<>(); // 돌 때마다 초기화
            for(int j = commands[i][0] - 1; j < commands[i][1]; j++){
                cal.add(array[j]); // array에서 읽어서 cal에 더한다
            }
            Collections.sort(cal); // 오름차순 정렬
            answer[i] = cal.get(commands[i][2] - 1);
        }
        return answer;
    }
}

 

 

 

맨 처음에 answer를 초기화 안해줘서 에러났음...

 

 

 

 

성능

 

 

 

 

---

 

다른 사람의 풀이

 

 

 

 

 

Arrays.copyOfRange를 사용했다. copyOfRange()는 배열을 복사하는 메소드이다.

 

Arrays.copyOfRange(원본 배열, 복사할 시작 인덱스, 끝 인덱스)   // 이렇게 사용한다.

 

temp 배열을 만들어서 잘라야하는 부분만큼 잘라서 복사했다. ㄷㄷㄷ

 

 

 

 

 

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int n = 0;
        int[] ret = new int[commands.length];

        while(n < commands.length){
            int m = commands[n][1] - commands[n][0] + 1;

            if(m == 1){
                ret[n] = array[commands[n++][0]-1];
                continue;
            }

            int[] a = new int[m];
            int j = 0;
            for(int i = commands[n][0]-1; i < commands[n][1]; i++)
                a[j++] = array[i];

            sort(a, 0, m-1);

            ret[n] = a[commands[n++][2]-1];
        }

        return ret;
    }

    void sort(int[] a, int left, int right){
        int pl = left;
        int pr = right;
        int x = a[(pl+pr)/2];

        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                int temp = a[pl];
                a[pl] = a[pr];
                a[pr] = temp;
                pl++;
                pr--;
            }
        }while(pl <= pr);

        if(left < pr) sort(a, left, pr);
        if(right > pl) sort(a, pl, right);
    }
}

 

 

 

음.... commands 값이 2 5 3 이면 5-3+1 개만큼 읽어오는 방법을 사용했다. 얘가 m이고

 

a라는 크기가 m인 배열을 만들어 그 안에 array에서 읽어온 값을 넣는다

 

sort라는 함수를 만들어 오름차순 정렬을 직접 구현했다.

 

정렬은 퀵 정렬을 사용하심... 정렬도 직접 구현해봐야 코딩이 느나보다!