[프로그래머스 알고리즘 Level1] K번째 수 (Java/정렬)

* 코딩 공부를 하며 기초를 다지기 위해 프로그래머스 알고리즘 공부를 시작한다.

Java언어를 주로 사용할 것이며 익숙해진 다음 다른 언어를 활용해 도전해 볼 것이다.

 

문제

---

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

입출력 예

---

arraycommandsreturn

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

 

(문제 출처:https://programmers.co.kr/learn/courses/30/lessons/42748#)

---

[문제에 대한 내 생각]

배열을 잘라내서

나는 Arrays.sort()를 이용해 정렬한 후

반복문을 돌려 답을 구한다.. 이 정도까지밖에 생각 못했다

다른 사람이 푼 문제를 참고하며 함수에 대해 더 찾아보고 공부해야겠다.

※고로.. 나는 문제를 풀지 못하였다...

괜찮아!! 공부하면 되니까!

 

다른분들의 풀이를 가지고 공부를 해보자!

(출처 1:https://sas-study.tistory.com/3)

(출처 2:https://dreamhollic.tistory.com/entry/Programmers-13-K%EB%B2%88%EC%A7%B8%EC%88%98-JAVA)

---

 

import java.util.*;
 
class Solution {
    public static int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int index = 0 ;
 
        for(int i = 0 ; i < commands.length ; i++)
        {
            int start = commands[i][0];
            int end = commands[i][1];
            int k = commands[i][2];
 
            int[] tmp = new int[end - start + 1];
 
            int a = 0;
            for(int j = start - 1 ; j < end ; j++)
                tmp[a++] = array[j];
 
            Arrays.sort(tmp);
            answer[index++] = tmp[k-1];
        }
        return answer;
    }
}

 

d※내 공부와 이해를 위해서 좀 세세하게 적어보겠습니다..!!

 

---

1) 먼저 문제를 이해해보자 

제한사항에서 commands의 각 원소의 길이는 3이라고 했다.  3은 각 i, j, k로 나타낸다

고로 commands [?][3]이라고 할 수 있다. 

원래 array배열에서 i번째부터 j번째까지 잘라내어 k번째 배열을 answer에 담는다

때문에 [?] 개수만큼 답이 되어야 하기 때문에 answer의 길이는 [?]와 같은 commands.length 가 된다.

 

2) 나중에 answer []에 넣을 index 변수를 지정해준다.

 

3) for문을 이용해 commands.length 미만만큼 반복해 준다.

 

4) start변수에 commands의 i번째 배열에 0번째 값(=i값)을 저장해준다.

똑같이 end 변수에 commands 의 i번째 배열에 1번째 값(=j값)을 저장해준다.

마지막으로 k변수에 commands 의 i번째 배열에 2번째 값(=k값)을 저장해준다.

 

5) [end(j)-start(i)+1] 길이의 배열 tmp를 선언

   *잘 이해 안 되는 부분..

6) int a=0; 을 선언

 

7) 반복문 안에 반복문을 추가하여 변수 j를 start-1로 선언한 후 end 미만까지 반복하도록 정의한다.

 

8) tmp [a++] 배열은 tmp배열이 0부터 증가하면서 array [j] 값들을 집어넣는다.

 

9) Array.sort(tmp) 배열 정렬 함수를 이용하여 tmp배열을 정렬한다.

 

10) answer배열에 0부터 증가시키면서 tmp [k-1]의 값을 집어넣는다..!!

 

11) answer을 리턴한다..!!

 

---

이렇게 이해를 해보았습니다.. 

다른 방법으로 해결된 코드도 많았지만 우선 이 정도에서 마치겠습니다.

추후 공부하며 추가를 진행할 것이고

정확한 이해와 설명이 서툴지만 차근차근 한 문제씩 풀어나가겠습니다!! 

 

 

+copyOfRange 함수를 공부하여 이용한 방법을 추가해보자!