[알고리즘] 프로그래머스 > 정렬 > 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 함수를 작성해주세요.

 

 

나의 풀이 (java)

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[] tempArray = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(tempArray);
            answer[i] = tempArray[commands[i][2]-1];
            System.out.println("### result !!  i : "+i+"  ,answer  : "+answer[i]);
        }
        return answer;
    }
}

 

내가 사용한 방법

Array library를 이용한 array 복사 후 정렬 

문제를 보자마자 들었던 생각은 array를 복사하는 method가 생각나서 해당 method를 검색 (copyOfRange)

그리고 그 array를 정렬할 수 있는 method(sort)가 있는 것도 알고 있었기에 풀이 방법은 어렵지 않았으나,

for문에서 필요한 data를 꺼내올때 index에서 -1 하는 부분에서 좀 헷갈렸음

• copyOfRange() - array의 index를 통한 범위만큼 복사
• Arrays.sort() - array 정렬

 

다른 사람의 풀이

• 나와 같이 Array 라이브러리를 이용해 문제를 해결한 사람이 가장 많아 보임 (대부분 콘셉트가 비슷함)
• 거의 유일하게 다른 풀이법은 직접 퀵 정렬을 구현하는 풀이가 남달랐음
  • 실무에서의 문제풀이라면 대다수가 풀었던 방식이 좋았겠으나, 연습하는 동안은 이렇게 직접 sort를 구현해서 문제를 푸는 게 점수도 많이 받고, 진짜 알고리즘 연습도 될 것 같다  다시 풀어보자

 

느낀점

몇 년 만에 제대로 하려다 보니, 감도 익힐 겸 가벼운 마음으로 시작했는데, 생각보다 잘 기억나지 않는다..

• 정렬 별 개념과 시간 복잡도 공부하기 (버블, 선택, 퀵, 힙) - https://yabmoons.tistory.com/250