[JAVA] 프로그래머스 | 42748 K번째 수

📝 TIL

- [프로그래머스] 42748 K번째 수

 

제한사항

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

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

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

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

 

 

입출력 예

입출력 #1

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

---

🦔 설계 및 시도

1. commands 전체 길이까지 for문 1번
2. 부분 배열을 찾기 위해 index 따라 for문 1번 > 리스트에 저장

3. Collections을 사용하여 정렬 

4. answer 배열에 담기 > 초기화

 

따라서 내가 푼 풀이는 다음과 같다

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        List<Integer> num = new ArrayList<>();
        
        for(int i = 0; i < commands.length; i++) {
        	// 부분 배열
            for(int j = commands[i][0] - 1; j < commands[i][1]; j++) {
                num.add(array[j]);
            }
            // 정렬
            Collections.sort(num); 
            answer[i] = num.get(commands[i][2] - 1); // K번째 수 선택
            num.clear(); // 다음 순회 위해 초기화
        }
        return answer;
    }
}

 

❌ 단점

- 이중 for문. 이 문제의 경우 commands의 길이가 50까지여서 괜찮았긴 하다!

- List에 값을 추가하고 -> 정렬하고 -> 추출 -> 초기화를 반복하기에 성능 저하 및 불필요한 코드

 

따라서 좀 더 나은 풀이를 찾아봤다.

 

🔥 풀이에 사용된 개념

Arrays.copyOfRange(arr, from, to)

- 배열의 일부를 복사하여 새로운 배열을 반환한다(부분 배열 같은 느낌)

- from은 포함, to는 미포함

 

Arrays 유틸 클래스의 배열의 일부를 복사하는 copyOfRange 메서드를 활용하여

부분 배열을 반환 방식을 사용하여 List를 사용하지 않는다.

---

 

💡 풀이 소스 코드

 

시간복잡도 : O(m*k log k) => 아주 단순화하면 O(n log n)

 

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

 

---

🚀 새로 배운 내용

- 유틸리티 클래스의 내장 메서드를 많이 공부하자

- copyOfRange를 이용하여 substring과 같은 부분 배열을 반환할 수 있다

 

 

---

😺  느낀점

자바의 유틸리티 클래스는 알면 알수록 도움이 되는 거 같다!

또 코딩 테스트에서는 docs가 제공되기 때문에 해당 공식 문서를 보는 연습도 하면 좋을 듯 하다

파이썬의 경우 docs가 가독성이 좋은데 java는 좀 어려운듯?

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이