K번째수/java/프로그래머스/Level1

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

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

<K번째수>

○ 못 풀어서 다른사람 풀이 참고(sort(), copyOfRange() 사용)

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
 
        for(int i=0; i<commands.length; i++){
            int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            answer[i] = temp[commands[i][2]-1];
        }
 
        return answer;
    }
}

- anwer의 범위를 commands의 길이만큼 잡아준다. (각 행마다 숫자 하나씩을 도출해야하기 때문)

- commands의 길이만큼 반복하여 answer의 i번지에 각각 k번지 수를 담도록 하자.

- 각 행의 i번째부터 k번째의 수를 담아낼 임의의 temp배열을 선언한다.

- temp 배열 내에 i번째부터 k번째 수 까지 담아낸다.

  Arrays.copyOfRange(배열명, 시작, 끝) : 배열의 시작과 끝을 정해서 배열로 복사하는 함수

- 복사한 temp 배열 내의 수를 오름차순으로 정렬한다.

  Arrays.sort(배열명) : 배열안에 있는 문자열, 영문자, 숫자 모두 오름차순으로 정렬시켜주는 함수

- 정렬이 완료된 temp배열 안에서 commands배열의 k번째 수(commands[i][2]-1)를 answer배열의 i번지에 담아준다.

- Arrays내의 함수를 사용할 경우에는 import구문을 추가해준다. 

 

○ sort()함수만 사용한 풀이

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int i=0;i<commands.length;i++) {
            int start = commands[i][0]-1;
            int finish = commands[i][1]-1;
            int pick = commands[i][2]-1;
            int temp[] = new int[finish-start+1];
            
            for(int j=start, k=0;j<=finish;j++, k++) {
                temp[k] = array[j]; // 5, 2, 6, 3
            }
            Arrays.sort(temp);  // 2, 3, 5, 6
            answer[i] = temp[pick];
        }
        return answer;
    }
}

- 배열복사 함수(Array.copyOfRange())를 사용하지 않고 반복문을 사용하여 temp배열에 뽑아낸 수를 담아낸다.

- 시작점, 끝점, 뽑아낼 수의 인덱스값을 start, finish, pick으로 선언한다. (가독성, 효율성 증가 됨)

- 복사할 temp배열의 길이는 finish-start+1로 선언한다.

- start 부터 finish까지의 수(j)를 temp배열에 담아준다. (temp는 0번지부터 하나씩 증가해야하므로 0부터 하나씩 증가하는 변수로 선언하였다)

- sort()함수로 정렬한 temp배열 안에서 commands배열의 k번째 수를 answer배열의 i번지에 담아주어야 한다.

  앞서 k번째의 수를 pick으로 선언해놓았기 때문에 temp[pick]으로 담아낸다.

 

○ 함수 없이 푼 풀이 (배열 복사, 향상된 Bubble Sort)

import java.util.Arrays;
 
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        boolean flag;
        
        for(int i=0;i<commands.length;i++){
            int start = commands[i][0]-1;
            int finish = commands[i][1]-1;
            int pick = commands[i][2]-1;
            int[] temp = new int[finish - start +1];
            
            // temp에 그 수만큼 담기
            for(int j=start, k=0;j<=finish;j++,k++) {
                temp[k] = array[j]; // 5, 2, 6, 3
            }
            
            for(int j=1;j<temp.length;j++) {
                flag = false;
                for(int k=0;k<temp.length-j;k++) {
                    if(temp[k]>temp[k+1]) {
                        temp[k] = temp[k]^temp[k+1];
                        temp[k+1] = temp[k+1]^temp[k];
                        temp[k] = temp[k]^temp[k+1];
                        flag = true;
                    }
                }
                if(flag==false)
                    break;
            }
            
            answer[i] = temp[pick];
        }
        
        return answer;
    }
}

- Bubble Sort를 이용하여 temp내의 수를 오름차순으로 정렬한다.

- boolean으로 flag값을 선언하여 스왑이 한번도 일어나지 않았을 경우는 false로 반복문을 종료하도록 한다.