여러가지/알고리즘 & 자료구조

[프로그래머스] k번째수

hyeseong-dev 2024. 10. 16. 16:15

K번째 수 찾기 알고리즘

문제 설명

배열의 특정 구간을 자르고, 그 구간을 정렬한 후, 정렬된 배열의 K번째 숫자를 찾는 문제입니다. 이를 통해 주어진 조건에 맞는 수를 구하는 과정을 연습할 수 있습니다.

예를 들어, 주어진 배열이 [1, 5, 2, 6, 3, 7, 4]이고, 명령어가 [[2, 5, 3], [4, 4, 1], [1, 7, 3]]인 경우를 살펴보겠습니다.

  1. 첫 번째 명령어: [2, 5, 3]

    • 배열의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
    • 이 배열을 정렬하면 [2, 3, 5, 6]이 됩니다.
    • 3번째 숫자는 5입니다.

  2. 두 번째 명령어: [4, 4, 1]

    • 배열의 4번째부터 4번째까지 자르면 [6]입니다.
    • 정렬 후 1번째 숫자는 6입니다.

  3. 세 번째 명령어: [1, 7, 3]

    • 배열의 1번째부터 7번째까지 자르면 [1, 5, 2, 6, 3, 7, 4]입니다.
    • 정렬 후 3번째 숫자는 3입니다.

위와 같은 과정을 통해, 최종적으로 구해진 결과는 [5, 6, 3]입니다.

제한사항

  • 배열의 길이는 1 이상 100 이하입니다.
  • 배열의 각 원소는 1 이상 100 이하입니다.
  • 명령어의 길이는 1 이상 50 이하입니다.
  • 명령어의 각 원소는 길이가 3입니다.

코드 구현

아래는 이 문제를 해결하기 위한 Java 코드입니다.

package lv1.k번째수;

import java.util.Arrays;

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

    public static void main(String[] args) {
        var main = new Solution();
        int[] a = {1, 5, 2, 6, 3, 7, 4};
        int[][] b = {{2, 5, 3}, {4, 4, 1}, {1, 7, 3}};
        System.out.println(Arrays.toString(main.solution(a, b))); // 출력: [5, 6, 3]
    }
}

코드 설명

  1. 배열과 명령어를 받는 메서드: solution 메서드는 배열과 2차원 명령어 배열을 매개변수로 받습니다.

  2. 명령어를 반복 처리: 각 명령어를 순회하면서 i번째부터 j번째까지의 부분 배열을 Arrays.copyOfRange 메서드를 사용해 잘라냅니다.

  3. 정렬 및 K번째 숫자 추출: 잘라낸 배열을 정렬한 후, K번째 숫자를 추출하여 결과 배열에 저장합니다.

  4. 결과 반환: 최종적으로 모든 명령어에 대한 K번째 숫자를 담은 배열을 반환합니다.

결론

이 문제는 배열의 특정 구간을 자르고 정렬한 후 K번째 숫자를 찾는 간단한 알고리즘을 통해, 배열 처리 및 정렬의 기초를 배울 수 있는 좋은 예제입니다. Java의 다양한 배열 및 정렬 메서드를 활용하여 간결하게 구현할 수 있습니다.

이와 같은 문제를 통해 기본적인 알고리즘 사고를 키우고, 실제 코딩 인터뷰나 알고리즘 대회에서 필요한 기초를 다질 수 있습니다.

저작자표시 (새창열림)