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

문제

번호

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

내용

배열 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입니다.

입출력 예

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

입출력 예 설명

[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입니다.

 

언어

JAVA

 

---

풀이

문제 해석

문제 자체는 간단한 문제이다.

1. commands의 요소를 모두 수행한다.
2. commands의 각 요소 중 첫번째 원소부터 두번째 원소까지 array를 자른다.
3. 자른 array를 크기 순으로 정렬한다.
4. array에서 commands의 세번째 원소 값의 위치에 있는 원소를 answer에 push한다.

 

주의해야할 점은 index의 파악이다.

commands의 각 원소는 "몇번째 인지"를 나타내는 것이지 "위치"를 나타내는 것이 아니다.

문제의 예에서 commands의 요소 중 하나가 [2, 5, 3]이었다.

그렇다면 이는 2번째, 5번째, 3번째를 나타내는 것이지, index가 2, 5, 3인 것을 나타내는 것이 아니다. 이것이 나타내는 index는 1, 4, 2이다.

그렇기에 commands의 각 원소에서 -1을 한 것이 index이다.

 

처음 시도한 코드

처음에는 Array List의 <pre>sublist</pre> 메소드를 이용하여 편하게 잘라내려 하였다. 그리고 <pre>get(index)</pre> 메소드도 지원하므로 index를 통하여서 요소를 쉽게 얻을 수 있기 때문에 장점이라고 생각하였다.

 

그러나 반복문의 두 번째 부터 list의 순서가 변화하였고, 이로 인해 실패하였다.

이는 List 인터페이스의 경우 순차성을 보장하지 않기 때문이라고 한다.

 

import java.util.*;

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

        List<Integer> list = new ArrayList<>();

        for(int i : array) {
            list.add(i);
        }

        for(int[] i : commands) {
            List<Integer> sublist = list.subList(i[0]-1, i[1]);
            Collections.sort(sublist);
            answer[count++] = sublist.get(i[2]-1);
        }
        
        return answer;
    }
}

 

문제 해결 1

결국 List의 <pre>sublist()</pre> 메소드를 활용하지 못하고 for 반복문을 통하여서 array를 자르게 되었다.

코드는 아래에 나와있다.

 

문제 해결 2

그런데 List가 아닌 Array에도 <pre>sublist()</pre>와 비슷한 기능을 지원하는 메소드가 있다고 한다.

사실은 비슷하진 않고 전혀 다르다. 다만, 비슷하게 사용할 수는 있다. 바로 <pre>copyOfRange()</pre>이다.

copyOfRange는 index를 이용하여 array의 일부를 잘라서 복사할 수 있다.

이 메소드는 값을 복사하는 것이기 때문에 원본에는 영향을 주지 않는다.

 

문제 해결 2번 코드를 보면 <pre>int[] subArr = Arrays.copyOfRange(array, i[0]-1,i[1]);</pre>로 되어있는데 이 때 잘 봐야할 것은 end index이다.

start처럼 -1이 되어 있지 않고 그대로 사용되고 있는데 이는 copyOfRange가 end index의 전까지만 복사하기 때문이다.

이에 주의하여 코드를 작성해야 할 것 같다.

 

---

코드

문제 해결 1

import java.util.*;

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

        for(int[] i : commands) {
            List<Integer> sublist = new ArrayList<>();
            for(int j = i[0]-1 ; j < i[1] ; j++) {
                sublist.add(array[j]);
            }
            Collections.sort(sublist);
            answer[count++] = sublist.get(i[2]-1);
        }

        return answer;
    }
}

 

문제 해결 2

import java.util.*;

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

        for(int[] i : commands) {
            int[] subArr = Arrays.copyOfRange(array, i[0]-1,i[1]);
            Arrays.sort(subArr);
            answer[count++] = subArr[i[2]-1];
        }

        return answer;
    }
}