[프로그래머스]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이라면

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

 

풀이과정

이 문제 진짜 어이없게 헤맨 문제임ㅋㅋㅋㅋ

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for(int i=0; i<commands.length; i++){
            int [] arr = array;
            quickSort(arr,commands[i][0]-1 ,commands[i][1]-1);
            answer[i] = arr[commands[i][0]-1+commands[i][2]-1];
        }
        return answer;
    }
    public void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = arr[right];
    
        int sortedIndex = left;
        for (int i = left; i < right; i++) {
            if (arr[i] <= pivot) {
                swap(arr, i, sortedIndex);
                sortedIndex++;
            }
        }
        swap(arr, sortedIndex, right);
        quickSort(arr, left, sortedIndex - 1);
        quickSort(arr, sortedIndex + 1, right);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

테스트 1

입력값 〉	[1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]]
기댓값 〉	[5, 6, 3]
실행 결과 〉	실행한 결괏값 [5,5,3]이 기댓값 [5,6,3]과 다릅니다.

answer[i] = arr[commands[i][0]-1+commands[i][2]-1];

→ 6으로 하나인 경우 여기가 해당이 안됨 이거 어떻게 해결하면 될듯

아니 근데 6 만 정렬하면 6이 나와야지 왜 뜬금없이 5가 튀어나옴?

정렬을 어떻게 했길래 그러는거야

Q. 무슨 일이 일어나고 있나요

궁금하지만 잠을 못 자서 너무 피곤해서 일단 케이스 빼서 통과하고 봄

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int i=0; i<commands.length; i++){
            int [] arr = array;
            
            if(commands[i][0]!=commands[i][1]){
                quickSort(arr,commands[i][0]-1 ,commands[i][1]-1);
            }
            answer[i] = arr[commands[i][0]-1+commands[i][2]-1];
        }
        return answer;
    }
    public void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = arr[right];
    
        int sortedIndex = left;
        for (int i = left; i < right; i++) {
            if (arr[i] <= pivot) {
                swap(arr, i, sortedIndex);
                sortedIndex++;
            }
        }
        swap(arr, sortedIndex, right);
        quickSort(arr, left, sortedIndex - 1);
        quickSort(arr, sortedIndex + 1, right);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

음 정렬 케이스 분리했는데도 똑같이 안 되니까 읽는게 잘못되고 있는 거 같음

테스트 1

입력값 〉	[1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]]
기댓값 〉	[5, 6, 3]
실행 결과 〉	실행한 결괏값 [5,5,3]이 기댓값 [5,6,3]과 다릅니다.

읽기 분리하고 테스트 케이스는 통과

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int i=0; i<commands.length; i++){
            int [] arr = array;
            if(commands[i][0]!=commands[i][1]){
                quickSort(arr,commands[i][0]-1 ,commands[i][1]-1);
                answer[i] = arr[commands[i][0]-1+commands[i][2]-1];
            }else{
                answer[i] = arr[commands[i][0]+commands[i][2]-1];
            }
        }
        return answer;
    }
    public void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = arr[right];
    
        int sortedIndex = left;
        for (int i = left; i < right; i++) {
            if (arr[i] <= pivot) {
                swap(arr, i, sortedIndex);
                sortedIndex++;
            }
        }
        swap(arr, sortedIndex, right);
        quickSort(arr, left, sortedIndex - 1);
        quickSort(arr, sortedIndex + 1, right);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

테스트 2 〉 실패 (0.04ms, 73.1MB)

테스트 7 〉 실패 (런타임 에러)

 

〉 실패 (런타임 에러)

런타임 에러는 보통 배열 인덱스 초과해서 읽으면 나던데 뭘까…

answer[i] = arr[commands[i][0]-1+commands[i][2]-1]; }else{ answer[i] = arr[commands[i][0]+commands[i][2]-1];

여기중에서 에러났을 거 같음

테스트 케이스에 1,1,1 이랑 7,7,1 넣어서 해봄

[1, 5, 2, 6, 3, 7, 4] [[1, 1, 1], [7, 7, 1]] [1, 4]

에러남

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 13 out of bounds for length 7
	at Solution.solution(Unknown Source)
	at SolutionTest.lambda$main$0(Unknown Source)
	at SolutionTest$SolutionRunner.run(Unknown Source)
	at SolutionTest.main(Unknown Source)

테스트 결과 (~˘▾˘)~
2개 중 1개 성공

if(commands[i][0]!=commands[i][1]){

예상한데 아니고 여기서 에러났다

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 13 out of bounds for length 7

엥 근데 commands는 3으로 정해져있는데 에러날게 뭐있어

테스트케이스 쪼개봄

[[7, 7, 1]] [4]

테스트 결과 (~˘▾˘)~
3개 중 1개 성공

지금 111 이랑 771이랑 둘 다 안 되고 있다

Index 7 out of bounds for length 7 이 뜨는걸 보니까 commends읽는게 문제가 아닌거같음

arr[commands[i][0]-1+commands[i][2]-1]

else의

answer[i] = arr[commands[i][0]+commands[i][2]-1] 여기서

arr[]의 index가 문제같음 아마

}else{
                answer[i] = arr[commands[i][0]-1+commands[i][2]-1];
            }

이 방식으로 하니까 다른 두개가 되는데

1번 테스트케이스 또 안됨ㅋㅋㅋㅋㅋㅋㅋ

테스트 1
입력값 〉[1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]]
기댓값 〉[5, 6, 3]
실행 결과 〉실행한 결괏값 [5,5,3]이 기댓값 [5,6,3]과 다릅니다.
테스트 2
입력값 〉[1, 5, 2, 6, 3, 7, 4], [[7, 7, 1]]
기댓값 〉[4]
실행 결과 〉테스트를 통과하였습니다.
테스트 3
입력값 〉[1, 5, 2, 6, 3, 7, 4], [[1, 1, 1]]
기댓값 〉[1]
실행 결과 〉테스트를 통과하였습니다.

6은 대체 뭐가 문제래?

[1, 5, 2, 6, 3, 7, 4] [4,4,1] [6]

아니 근데 웃긴게 케이스 이렇게 분리하니까 또 쟤는 잘 됨;

테스트 1
입력값 〉	[1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]]
기댓값 〉	[5, 6, 3]
실행 결과 〉	실행한 결괏값 [5,5,3]이 기댓값 [5,6,3]과 다릅니다.
테스트 2
입력값 〉	[1, 5, 2, 6, 3, 7, 4], [[4, 4, 1]]
기댓값 〉	[6]
실행 결과 〉	테스트를 통과하였습니다.

오 근데 이제 런타임 에러는 안 난다

테스트 1 〉 통과 (0.06ms, 74.9MB)

테스트 2 〉	실패 (0.04ms, 81.5MB)
테스트 3 〉	통과 (0.04ms, 73.5MB)
테스트 4 〉	통과 (0.03ms, 74.9MB)
테스트 5 〉	통과 (0.04ms, 65.3MB)
테스트 6 〉	통과 (0.02ms, 74.7MB)
테스트 7 〉	통과 (0.04ms, 82MB)

어차피 저렇게 케이스분리해봤자 테스트케이스 통과 못해서 그냥 if문 다시 삭제함

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int i = 0; i < commands.length; i++){
            int [] arr = array;
            quickSort(arr,commands[i][0]-1 ,commands[i][1]-1);
            answer[i] = arr[commands[i][0]-1+commands[i][2]-1];
        }
        return answer;
    }

 

[[2, 5, 3], [4, 4, 1], [1, 7, 3]]

commands[i][0]-1 :1

commands[i][1]-1 :4

commands[i][2]-1 :2

commands[i][0]-1+commands[i][2]-1 :3

arr[commands[i][0]-1+commands[i][2]-1] :5

1

2

3

5

6

7

4

commands[i][0]-1 :3

commands[i][1]-1 :3

commands[i][2]-1 :0

commands[i][0]-1+commands[i][2]-1 :3

arr[commands[i][0]-1+commands[i][2]-1] :5

1

2

3

5

6

7

4

commands[i][0]-1 :0

commands[i][1]-1 :6

commands[i][2]-1 :2

commands[i][0]-1+commands[i][2]-1 :2

arr[commands[i][0]-1+commands[i][2]-1] :3

1

2

3

4

5

6

7

---

로그 찍어봄

엥 약간 이상하게 동작하는 거 같음

왜 정렬이 되어있지?

quickSort(arr,3 ,3); 으로 갔으면 바로 돌아와야 되는디 left ==right라?

아 내가 배열을 깊은 복사를 안 하고 얕은 복사를 해서 값이 바뀐채로 그 다음으로 넘어간 거 같다…

완전 주의해야겠네

⚠️🚨배열 읽기용도로 카피할때 얕은복사 하면 안돼

⭐Java array deep copy 쉽게 할 수 없을까

1. clone

we’ll copy an array of primitive types using the clone method:
int[] array = {23, 43, 55, 12};
int[] copiedArray = array.clone();

2. stream

String[] strArray = {"orange", "red", "green'"};
String[] copiedArray = Arrays.stream(strArray).toArray(String[]::new);

제출 코드

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int i = 0; i < commands.length; i++){
            int [] arr = array.clone();
            quickSort(arr,commands[i][0]-1,commands[i][1]-1);
            answer[i] = arr[commands[i][0]-1+commands[i][2]-1];
        }
        return answer;
    }
    public void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = arr[right];
    
        int sortedIndex = left;
        for (int i = left; i < right; i++) {
            if (arr[i] <= pivot) {
                swap(arr, i, sortedIndex);
                sortedIndex++;
            }
        }
        swap(arr, sortedIndex, right);
        quickSort(arr, left, sortedIndex - 1);
        quickSort(arr, sortedIndex + 1, right);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}