AlgorithmProgrammers

프로그래머스 K번째수

, ,

1. 문제 링크

프로그래머스 K번째수

2. 문제 조건

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

2.1. 제한사항

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

3. 컴퓨팅 사고

K번째수는 정렬문제입니다. 문제에서 말해주는 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제입니다.

  • i번째 숫자부터 j번째 숫자까지 자르고 나서 ArrayList를 사용하여 값들을 담아주게 하였습니다.
  • 해당 값들은 Collections.sort()함수를 사용하여 오름차순으로 정렬시켜주었습니다.
  • 리스트를 순회하면서 리스트의 인덱스값과 k-1값이 같은경우 answer값에 담아주었습니다. 왜 k-1의 값과 인덱스값을 비교하였을까요. i번째는 1부터 시작하고 배열이 0번 인덱스부터 할당되어 있기때문에 이렇게 풀이해주었습니다.

K번째수 예시

1
2
3
4
5
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입니다.

여기서 주의할점은 command가 2차원배열로 주어진다는것입니다. 그렇기때문에 commands [[2, 5, 3], [4, 4, 1], [1, 7, 3]] 의 경우 배열하나당 하나의 경우라고 생각하셔야합니다. return값이 3개를 반환하는것을 보면 확인하실 수 있습니다.

기존의 값들이 변하면 안되기때문에 해당 배열을 Arrays.copy() 를 사용하였고 List의 값을 매번 경우의 수마다 clear()시켜서 갱신시켜주었습니다. 갱신을 시켜주지 않으면 기존의 값들과 섞여서 올바르지 않은 결과값을 노출합니다.

시간복잡도
시간복잡도 같은 경우는 command.size를 N, array.size를 M으로 놓으면
O(N*M) 이라고 할 수 있습니다. command의 길이는 1~50이하, arrays의 길이는 1~100이하 이기때문에 시간복잡도의 5000번의 정도의 연산이 이루어지므로 1초의 시간제한에 문제가 없습니다.

4. 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.ArrayList;
import java.util.Collections;

public class k번째수 {
    public static void main(String[] args) {

        int[] array = {1, 5, 2, 6, 3, 7, 4};
        int[][] commands = {{2, 5, 3}, {4, 4, 1}, {1, 7, 3}};

        ArrayList<Integer> ans = new ArrayList<>();
        for(int i=0; i<commands.length; i++){
            int copy[] = array.clone();
            int start = commands[i][0];
            int end = commands[i][1];
            int k = commands[i][2];

            for(int j=start-1; j<end; j++){
                ans.add(copy[j]);
            }
            Collections.sort(ans);

            for(int m=0; m<ans.size(); m++){

                if(m == k-1){
                    System.out.println(ans.get(k-1));
                }
            }
            ans.clear();
        }
    }
}

Share