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

 

❤️ Problem

• 문제
  배열 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 함수를 작성해주세요.
  
  

• 제한 사항
  • array의 길이는 1 이상 100 이하입니다.
  • array의 각 원소는 1 이상 100 이하입니다.
  • commands의 길이는 1 이상 50 이하입니다.
  • commands의 각 원소는 길이가 3입니다.

 

• 입출력 예 & 설명

no	array	commands	return
1	[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

1. [1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
   [1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
   [1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

---

 

💛 Solution

풀이 1

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 end = commands[i][1]-1;
            int point = commands[i][2]-1;

            int[] sorting = new int[end-start+1];
            int index = 0;
            for(int j=start; j<=end; j++) {
                sorting[index] = array[j];
                index++;
            }
            Arrays.sort(sorting);
            answer[i] = sorting[point];
//            System.out.println(answer[i]);
        }
        return answer;
    }
}

 

처리속도 SO SO🤔

---

풀이 2

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 end = commands[i][1];
            int point = commands[i][2]-1;

            int[] sorting = Arrays.copyOfRange(array, start, end);
            Arrays.sort(sorting);
            answer[i] = sorting[point];
            System.out.println(answer[i]);
        }
        return answer;
    }
}

 

처리속도 imporved?😅

 

---

 

💜 Comment

이 문제는 배열의 특정 구간(commands[i][0]부터 commands[i][1])의 값을 추출하는 게 포인트인 것 같다. 그리고 함정이라고 한다면 배열의 n번째 위치로 주어지는 commands[i][2]가 실제 배열의 인덱스처럼 0으로 시작하지 않기 때문에 반드시 -1을 해주어야 한다는 점이다.

풀이 1에서는 for 반복문을 사용해서 int[] array의 commands[i][0]부터 commands[i][1]까지의 배열을 int[] sorting으로 직접 대입하는 방식을 사용한 뒤, Array.sort()를 사용해서 정렬하였다. 그 다음 commands[i][2]-1 에 해당하는 위치의 sorting 값을 추출해서 int[] answer에 집어 넣어서 반환하면 끝!

풀이 2에서는 for 반복문으로 직접 배열을 복사하지 않고 Arrays.copyOfRange()를 사용해서 배열을 복사하는 방식을 사용했다. for 반복문을 쓰지 않으니 코드 성능이 올라가지 않을까 기대했는데 생각보다는 유의미한 차이가 있진 않았다.

 

 

캡쳐를 깜빡했다..😁💦 9069위!