K번째수

코딩테스트 준비를 위해 '프로그래머스'를 활용해보기로 했다.

이번 글은 레벨 1 정렬인 K번째수에 대한 풀이 방법을 적어보고자 한다.

1. 문제

문제는 아래와 같다. 출처

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

사실 나는 commands 배열의 의미가 뭔지 몰랐다.
코딩테스트는 문제를 잘 이해해야 한다는것을 깨닫게 된 경험이였다.

commands배열은 2차원 배열로 각 원소들의 의미는 각각의 테스트케이스이고, 하나의 원소는 array배열에서 추출할 시작위치, 끝위치, 정렬 후 획득값의 위치를 의미한다.

예시를 읽어보면 더 이해가 쉬울거라 생각한다.예시

2. 풀이

이러한 문제이해를 기반으로 답으로 하는 answer 배열을 구해보자!
1. 일단, solution 클래스의 solution 함수는 2개의 매개변수를 가지고 있다. 기본 배열array와 원하는 값을 의미하는 commands배열이 이것이다.

commands배열을 통해 결과 answer배열의 크기를 결정지을 수 있다.
요구한만큼 output이 나올것이기 때문이다.

다음은 for문을 통해 임시배열 tempArr을 만들고 그 배열을 정렬한다. 마지막으로 원하는 위치의 값을 결과 answer배열에 삽입한다.

위의 글을 코드로 작성하면 아래와 같다.

import java.util.*;

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

3. 깨달은 점

알고리즘 문제를 처음 풀어본 느낌은 문제이해를 잘 해야한다는 것이다.
그리고 오타가 나기 쉽기 때문에 나 스스로를 믿지 말아야 한다는 것!
마지막으로 import와 라이브러리 클래스들을 알고 있으면 훨씬 쉬워진다는 것이다.

정리하자면,
1. 문제이해를 잘 하자!
2. 오타는 언제어디서나 발생!
3. 기본지식은 많을 수록 좋다!

이상으로 알고리즘 첫 포스팅을 마친다.