[프로그래머스 : 레벨1] K번째 수 : 선택정렬(Java)

이번 문제는 라이브러리를 활용하여서 문제를 풀었는데 이번엔 문제가 좀 쉬워서

라이브러리를 사용하지 않고도 문제를 풀어봤다.

 

레벨 1이라서 그런지 쉬운편이였다.

 

문제 설명

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

 

제한사항

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

입출력 예

array	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입니다.

 

라이브러리를 활용한 문제 풀이 

import java.util.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = {};
        
        //answer 베얄 크기 결정
        answer = new int[commands.length];
        
        for(int i = 0; i< commands.length;i++){
        	// 배열 복사
            int[] temp = Arrays.copyOfRange(array, commands[i][0]-1,commands[i][1]);
            // 복사한 배열 정렬
            Arrays.sort(temp);
            //K번째 수 입력
            answer[i] = temp[commands[i][2]-1];
        }        
        
        return answer;
    }
}

이렇게 활용하였는데 copyOfRange() 메소드가 뭔지 궁금하다면 아래 링크를 통해서 확인 해보면 될거 같다.

 

https://wpioneer.tistory.com/99?category=1023662 

[Java] 배열 복사 하는 방법 ( clone(), copyOf(), copyOfRange() )

 

라이브러리를 활용하지 않고 직접 구현한 문제풀이 : 

 

import java.util.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = {};
        
        //answer 베얄 크기 결정
        answer = new int[commands.length];
        
        //제일먼저 해야할것
        //1. commands의 원소에 접근을 해야한다.
        for(int i = 0; i< commands.length;i++){
        	//복사할 배열의 길이 지정
            int[] temp = new int[commands[i][1] - commands[i][0] + 1];
            int index = 0;
            //i부터 j까지의 값 입력
            for(int j = commands[i][0]-1;j< commands[i][1] ;j++){
                temp[index++] = array[j];
            }
            //정렬 함수 호출
            int[] as = sort(temp);
            //K번째 값 입력
            answer[i] = as[commands[i][2]-1];
        }        
        
        return answer;
    }
    public int[] sort(int[] arr){
    	//매개변수 arr의 값 복사
    	int[] result = arr.clone();
        for(int i = 0; i<result.length;i++){
            for(int j = i+1; j<result.length; j++){
            	//다음거랑 비교했을때 크면 서로 값 바꾸기
                if(result[i] > result[j]){
                    int temp = result[i];
                    result[i] = result[j];
                    result[j] = temp;    
                }
            }
        }
        return result;
    }
}

 

위처럼 선택 정렬을 통해서 배열의 값들을 바꿔주면 된다.

 

내가 위 문제를 아래와 같이도 풀어보았다.

    public int[] solution(int[] array, int[][] commands) {
        int[] answer = {};
        
        //answer 베얄 크기 결정
        answer = new int[commands.length];
        
        //제일먼저 해야할것
        //1. commands의 원소에 접근을 해야한다.
        for(int i = 0; i< commands.length;i++){
            int[] temp = new int[commands[i][1] - commands[i][0] + 1];
            int index = 0;
            for(int j = commands[i][0]-1;j< commands[i][1] ;j++){
                temp[index++] = array[j];
            }
            System.out.println("정렬 전 : "+Arrays.toString(temp));
            sort(temp);
            System.out.println("정렬 후 : "+Arrays.toString(temp));
            answer[i] = temp[commands[i][2]-1];
        }        
        
        return answer;
    }
    public void sort(int[] arr){
    	int[] result = arr.clone();
        for(int i = 0; i<arr.length;i++){
            for(int j = i+1; j<arr.length; j++){
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;    
                }
            }
        }
    }

사실 둘의 차이는 sort에서 매개변수 배열을 복사해서 정렬한후 리턴해주느냐

아니면 매개변수로 받은 배열을 정렬을 해주느냐 그 차이인대 채점을 통해서 확인해보니 배열을 복사해서 정렬한후 리턴해주는게 속도가 더 빨랐던것 같다. 아무래도 매개변수로 받은 배열의 주소를 찾아가서 값을 바꾸다 보니 시간이 

좀더 오래 걸린듯하다.

 

 

느낀점

1. 쉬운건 라이브러리를 직접 구현해보자.

2. 주소를 찾아가 값을 변경해주는게 복잡할땐 배열을 복사해서 복사한 배열을 리턴하는 방식을 사용하는게

더 효율적이다. 

3. 매개변수로 주소만 받아도 해당 주소의 배열의 값을 변경하는게 가능하다.

4. 선택정렬을 할땐 for문 안의 for문의 초기화 값은 i+1이다.