K번째 수

· 문제 설명

배열 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]

 

---

· Thinking 1

comands 배열의 원소의 갯수 : commands.length

array : [1, 5, 2, 6, 3, 7, 4]
s : [2, 4, 1]
e : [5, 4, 7]
p : [3, 1, 3]

i = 0 ; i < 3

i = 0
j = s.get(0) : 2 ; j < e.get(0) : 5
array[2-1] 5
array[3-1] 2
array[4-1] 6
array[6-1] 3

i = 1
j = s.get(1) : 4 ; j < e.get(1) : 4
array[4-1] 6

i = 2
j = s.get(2) : 1; j < e.get(2) : 7
array[0]
...

 

==> 이걸 각각으로 또 담아야...
commands.length 만큼 배열을 만들어야함

 

---

· Thinking 2

그냥 첫번째만 해보자..!

 

array : [1, 5, 2, 6, 3, 7, 4]
i = 0
j = s.get(0) : 2 ; j < e.get(0) : 5
array[2-1] 5
array[3-1] 2
array[4-1] 6
array[6-1] 3

 

for (int i = s.get(0); i <= e.get(0); i++) {
	ArrayList<Integer> temp = new ArrayList<Integer>(e.get(0) - s.get(0) + 1);
		for(int j = 0; j < (e.get(0) - s.get(0) + 1); j++) {
			temp.add(array[i-1]);
		}
	System.out.println(temp);
}

 

출력값
[5, 5, 5, 5]
[2, 2, 2, 2]
[6, 6, 6, 6]
[3, 3, 3, 3]

 

이걸 이렇게 만드네..???? 

temp라는 Arraylist는 배열이 4개인데  총 배열은 하나??

 

for (int i = s.get(0); i <= e.get(0); i++) {
	temp.add(array[i-1]);
}
        
System.out.println("자른 배열 : "  + temp); // 자른 배열 : [5, 2, 6, 3]
Collections.sort(temp);
System.out.println("반환값 : "  + temp.get(p.get(0)-1)); // 출력잘됨

---

· Thinking 3

되는 코드로 각각 따로따로 테스트해보기..

ArrayList<Integer> temp = new ArrayList<Integer>();
ArrayList<Integer> temp2 = new ArrayList<Integer>();
ArrayList<Integer> temp3 = new ArrayList<Integer>();

for (int i = s.get(0); i <= e.get(0); i++) {
	temp.add(array[i-1]);
}
System.out.println("자른 배열 : "  + temp);
Collections.sort(temp);
System.out.println("반환값 : "  + temp.get(p.get(0)-1));
        
for (int i = s.get(1); i <= e.get(1); i++) {
	temp2.add(array[i-1]);
}
System.out.println("자른 배열 : "  + temp2);
Collections.sort(temp2);
System.out.println("반환값 : "  + temp2.get(p.get(1)-1));
        
for (int i = s.get(2); i <= e.get(2); i++) {
	temp3.add(array[i-1]);
}
System.out.println("자른 배열 : "  + temp3);
Collections.sort(temp3);
System.out.println("반환값 : "  + temp3.get(p.get(2)-1));

이게 지금 반복되니까 반복문으로 합쳐야됨...!!

 

for(int i = 0 ; i < commands.length ; i ++) {
	ArrayList<Integer> temp = new ArrayList<Integer>();
		for (int j = s.get(i); j <= e.get(i); j++) {
			temp.add(array[j-1]);
			Collections.sort(temp);
         }
	System.out.println("자른 배열 : "  + temp);
	System.out.println("반환값 : "  + temp.get(p.get(i)-1));
}

출력값
자른 배열 : [2, 3, 5, 6]
반환값 : 5
자른 배열 : [6]
반환값 : 6
자른 배열 : [1, 2, 3, 4, 5, 6, 7]
반환값 : 3

오 나이스 된다!!!!!!!!!!!!

---

· 완성 코드

import java.util.Collections;
import java.util.ArrayList;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        ArrayList<Integer> s = new ArrayList<Integer>(commands.length);
        ArrayList<Integer> e = new ArrayList<Integer>(commands.length);
        ArrayList<Integer> p = new ArrayList<Integer>(commands.length);
        
        for (int i = 0; i < commands.length; i++) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            s.add(commands[i][0]);
            e.add(commands[i][1]);
            p.add(commands[i][2]);
            
            for (int j = s.get(i); j <= e.get(i); j++) {
                temp.add(array[j-1]);
                Collections.sort(temp);
            }    
            answer[i] = temp.get(p.get(i)-1);
        }
        
        return answer;
    }
}

 

---

· 문제 출처

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

알고리즘 연습 - K번째수 | 프로그래머스