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 함수를 작성하세요.

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

📸 제한 사항

1) array의 길이는 1 이상 100 이하입니다.

2) array의 각 원소는 1 이상 100 이하입니다.

3) commands의 길이는 1 이상 50 이하입니다.

4) commands의 각 원소는 길이가 3입니다.

🗣 입출력 예시

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

먼저 2차원 commands 배열의 첫 번째 인덱스를 바탕으로 설명을 하면 array 배열을 i와 j의 크기만큼 2번째부터 5번째까지 자른 후 정렬을 합니다. 그러면 [2. 3. 5. 6]이라는 배열로 나뉘어지고 여기서 k 번째 즉 3번째 값은 현재 5라는 것을 알 수 있습니다.

 

이런 방식으로 두 번째 인덱스에 대한 풀이를 한다면 i와 j가 둘 다 4이니 [6] 이라는 배열이 생성되며 이 곳에서 k 번째 즉 1번째 값은 현재 6입니다. 또한 이제 마지막으로 세 번째 인덱스의 i와 j의 값이 1과 7이기 때문에 array 배열을 1번째부터 7번째까지 자르게 됩니다. 그러면 [1, 2, 3, 4, 5, 6, 7]이라는 배열이 생성되며 이 배열 안에서 k번째 즉 3번째 값은 현재 3이라는 것을 알 수 있습니다.

 

📨 나의 해결책 (40분 소요)

# solution 메소드

solution 메소드에서는 array 배열과 2차원 commands 배열을 매개변수로 전달 받습니다. 그 후 commands 2차원 배열의 크기만큼 answers 배열을 생성하며 for each 문을 통해 answers 배열에 findData 함수를 호출해 리턴 값을 저장하고 있습니다.

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

    for (int[] command : commands) {
        answers[count++] = findData(array, command[0], command[1], command[2]);
    }

    return answers;
}

# findData 메소드

findData 메소드는 위에서 solution 메소드의 for each 문에서 호출되며 array 배열과 commands 2차원 배열의 간 인덱스에 해당하는 i, j ,k 값을 매개변수 start, end, k로 전달받고 있습니다. 그 후 array 배열을 start와 end 값에 따라 잘라주어야 합니다.

 

따라서 newArray라는 정수형 배열을 새롭게 생성해주고 있으며 start와 end의 값에 맞게 newArray 배열로 array 배열의 값을 for문을 통해 복사해주고 있으며 복사가 모두 끝났다면 Arrays 클래스의 sort 메소드를 활용하여 newArray 배열을 오름차순으로 정렬해줍니다. 그러면 이제 거의 모든 것이 끝났으며 최종적으로 newArray 배열에 k 번째 해당하는 값을 리턴해주면서 종료됩니다.

public int findData(int[] array, int start, int end, int k) {
    int[] newArray = new int[(end - start) + 1];
    int count = 0;

    for (int i = start - 1; i < end; i++) {
        newArray[count++] = array[i];
    }
    Arrays.sort(newArray);
    return newArray[k - 1];
}

[ 전체 소스코드 ]

import java.util.Arrays;

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

        for (int[] command : commands) {
            answers[count++] = findData(array, command[0], command[1], command[2]);
        }

        return answers;
    }

    public int findData(int[] array, int start, int end, int k) {
        int[] newArray = new int[(end - start) + 1];
        int count = 0;

        for (int i = start - 1; i < end; i++) {
            newArray[count++] = array[i];
        }
        Arrays.sort(newArray);
        return newArray[k - 1];
    }
}

🎨 모범 답안 (정렬)

이번 문제의 모범 답안 코드는 아래와 같습니다. 코드의 전체적인 로직은 제가 구성한 코드와 매우 유사합니다. 그러나 한 가지 다른 점이라면 Arrays 클래스의 copyOfRange 메소드를 사용하여 array 배열 값을 temp 배열로 i와 j 값을 매개변수로 전달하면서 for 반복문을 사용하지 않고 훨씬 더 간단한 방식으로 배열을 복사하고 있습니다. 그러나 테스트 속도는 제 코드가 조금 더 빨랐습니다.

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;
    }
}

👍 글을 마치며

오늘은 코딩 테스트 연습 문제 중 K번째 수라는 문제를 풀어보았습니다. 이번 문제는 이전에 풀었던 문제들에 비해 상대적으로 난이도는 낮지만 배열을 활용해서 로직을 구현해보는 좋은 공부가 되었던 것 같습니다. 코딩 테스트 연습 문제를 조금씩 풀어보면서 이제는 새로운 문제를 보아도 겁먹지 않고 풀 수 있다는 자신감을 얻게 되었으며 앞으로도 꾸준히 문제를 열심히 풀어보도록 하겠습니다.