[알고리즘] 프로그래머스 K번째 수 (레벨 1) / 자바 java 풀이

 

 

프로그래머스 정렬 문제 중 K 번째 수 구하기 문제이다. 

 

레벨 1 짜리 문제라 엄청 어렵지는 않게 풀었는데 다른 사람들의 풀이를 보니 역시나 입이 떡 하고 벌어졌던 문제였다.

 

📑  K번째 수

🔗 https://school.programmers.co.kr/learn/courses/30/lessons/42748

문제 설명

배열 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 함수를 작성해주세요.

---

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1이상 100이하 입니다.
• commands의 길이는 1이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

---

입출력 예

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

 

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

✏️ 문제 해결 방법

commands 배열에 주어진 숫자들은 다음과 같다.

• commands[i][0] = 시작 번호
• commands[i][1] = 끝 번호
• commands[i][2] = 구해야 하는 배열의 번호K

commands.length 길이만큼 반복하고 commands.length 길이만큼의 answer 배열을 만들어서 요구사항대로 정렬을 마친 후 번호를 구해 i 번째 배열에 구해야 하는 번호를 넣으면 된다.

 

1. 정답 배열

정답 배열은 commands 배열의 길이만큼 만들어진다. 

int[] answer = new int[commands.length];

 

2. 정렬하고 

commands.length 만큼 정렬하고 K 번째 수를 구한다.

for(int i = 0 ; i < commands.length ; i++) {
	
    int start = commands[i][0];
    int end = commands[i][1];
    int K = commands[i][2];
    
    // 정렬시켜줄 배열
    int[] arr = new int[end - start + 1];
    int idx = 0;
    
    for(int j = start - 1; j < end ; j++) {
    	
        arr[idx++] = arr[j];
        
	}
    Arrays.sort(arr);
    answer[i] = arr[K - 1];
}

 

위의 코드를 모두 합치면 다음과 같다.

 

 

전체 코드

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        
        int[] answer = new int[commands.length];
        
        for(int i = 0 ; i < commands.length ; i++) {
            
            int start = commands[i][0];
            int end = commands[i][1];
            int K = commands[i][2];
            
            int[] arr = new int[end - start + 1];
            int idx = 0;
            
            for(int j = start-1 ; j < end ; j++) {
                
                arr[idx++] = array[j];
                
            }
            
            Arrays.sort(arr);
            answer[i] = arr[K - 1];
            
        }
        return answer;
    }
}

 

🕸️ 문제 풀이 소감

위에서 말 했듯이 다른 사람들의 풀이를 보고 많이 놀랐던 문제이다.

Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);

이 메서드를 사용함으로써 전체 코드의 길이를 다섯줄로 줄였다. 그리고 이전에 풀이를 살펴봤는데 이전에는 ArrayList<int[]> 리스트 자료구조를 사용하여 풀었었다. 이전 풀이보다 훨씬 간단해진 느낌이라 이번 풀이가 더 마음에 든다 : ) 훨씬 알아보기 쉬운 듯 하다. 풀 때 마다 다르게 푸는 것도 신기하다~

---

궁금한 점이 있거나 잘못된 부분이 있다면 얼마든지 댓글로 남겨주세요 🤗

감사합니다!

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."