[Algorizym-Java] K번째 수( Programmers coding test) {My First resolve!}

안녕하세요! 학기를 정신없이 마무리 짓고 오랜만에 다시 글을 작성하게 되었습니다. 

프로그래머스 백엔드 교육과정을 준비하면서 선발 과정에 포함되어있는 코딩테스트를 준비하기 위해 알고리즘 문제풀이를 하고난 뒤 풀면서 느꼈던 어려움. 풀이를 하는데 사용했던 java package, 그리고 좋은 정답의 예시를 다시한번 정리하기 위해서 글을 작성하게 되었습니다. 

---

문제설명

k번째 수 문제설명

정답코드 (훨씬 좋은 예시의 정답들이 있습니다. 프로그래머스 홈페이지에 문제를 검색해보시면 확인 가능합니다. )

 

다른 사람들의 풀이 보러가기 : https://programmers.co.kr/learn/courses/30/lessons/42748/solution_groups?language=java

import java.util.Arrays;
import java.util.ArrayList;

public class kNumber {

        public int[] solution(int[] array, int[][] commands) {

            int j = 0;

            // 매개로 입력받은 배열의 크기만큼 동적으로 생성
            int[] answer = new int[commands.length];
            ArrayList<Integer> ansList = new ArrayList<Integer>();
            
            // 반복문을 돌면서 부분 배열을 취하고, 해당 배열을 정렬하고 난 뒤 K번째 위치인 targetIndex를 ArrayList에 추가.
            for(int i = 0; i < commands.length; i++) {

                int fromIndex = commands[i][0];
                int toIndex = commands[i][1];

                if(fromIndex == toIndex){

                    int tmp = array[--fromIndex];
                    ansList.add(tmp);
                    continue;
                }

                if(fromIndex != 0) fromIndex--;
                //여기가 문제였어.. 자바 copyOfRange()메소드는 to 인덱스를 자동으 -1해주는데 그걸 망각하고 한번 더 했던거임..
                // if(toIndex != array.length) toIndex++; (불필요한 연산이므로 주석처리.)

                int[] tempArr = Arrays.copyOfRange(array, fromIndex, toIndex);
                Arrays.sort(tempArr);
                int targetIndex = commands[i][2];

                ansList.add(tempArr[--targetIndex]);
            }
            
            // Enhanced for (for-each) 사용 예시 
            for (int i : ansList) {
                answer[j] = i;
                j++;
            }
            
            return answer;
        }
    }

 

 

문제를 풀이하면서 testcase 한 개가 오답을 뱉는 문제가 있었는데,  결국에는 indexing 을 잘못 다루었던 오류였습니다....

자바의 배열의 부분배열을 취하는 패키지 매서드인 copyOfRange() 메서드의 부분배열의 마지막 인덱스를 자동으로 -1해주는데, 

그걸 생각하지 못하고 인덱스를 더해버려서 문제가 발생했던 것 같습니다. 

 

추후에 시간복잡도를 계산하는 업데이트를 하겠습니다.

감사합니다!