재귀함수와 정렬(2)

김민지·2023년 1월 13일

코딩테스트

목록 보기

19/31

10989: 정렬 다시

퀵정렬

처음시도는 맞았지만 여러 메서드를 정의해서 메서드를 stack에 쌓고 하면 시간이 조금 더들어서그런건지?(유의미하게 시간이 더 걸리는 지는 잘 모르겠다) 시간초과가 뜬다
s대신 e를 사용해도는 되지만 왜 시간초과가 뜨는진 잘 모르겠다
조금더 시간이 널널한 문제(2750)에서는 s를 사용하든 e를 사용하든 정답이 뜬다

코드

public static void sort(int arr[], int start, int end){
        int s = start;
        int e = end;
        //중간값으로 아무거나 잡아준다
        int pivot = arr[start];
        //등호가 왜필요한가
        //++과 --을 해주기 위함인듯

        //s=e기점으로, 그순간의 왼쪽애들은 pivot보다 작을것이고 그순간의 오른쪽애들은 pivot보다클것이다
        //그런데 s는 +1이 되고 e는 -1이된다. -> 아님 항상 s와 e는 2차이가 아님 while문에서 s++이계속돼서 s>e되는 경우
        //정확히 2의 차이가 안날수있음

        while(s<e){
            while(arr[e] > pivot) e--;
            while(s<e &&arr[s] <= pivot) s++;

                int temp = arr[s];
                arr[s] = arr[e];
                arr[e] = temp;
        }
        arr[start] = arr[e];
        arr[e] = pivot;
        //e는 안되고 s만 됨 s대신 e를 넣게 되면 stackoverflow터짐
        //둘이 같게되는순간이있는데 if문과 while문의 등호로 인해 s는 커지고 e는 작아지게된다
        //그러니까 s=e인
        if(start < s-1) sort(arr,start, s-1);//e여도 통과
        //s++되다보니 end랑 같아지거나 커질수있을듯 그런경우를 제외해주어야한다
        if(s+1< end) sort(arr,s+1, end);//e여도 통과

    }

count

0 3 1 1 2 가 있다고 하자
원본배열과 counting 배열 그리고 결과를 담을 배열을 만든다고하자
counting배열은 원본배열에서 가장 큰 숫자 만큼을 만들어주면된다
0,1,2,3을 담을 수 있도록 가장큰숫자 +1만큼의 배열을 만들어주면된다
count를 해주는 이유는 count한대로 숫자를 넣어줄것이기때문이다
counting의 배열의 원소의 값은 개수를 의미한다
1 2 1 1
누적합
1 3 4 5
idx=0 즉 1은
0이하의값이 1개 있다는 의미고
idx=1 즉 3은
1이하의 값이 3개있다는 의미이다
counting[arr[i]]은 arr[i]의 값이 예를들어 3이라고 했을때 5를 뱉는다. 여기서 1을 빼주어야 arr[i]의 값이다
arr[i]는 단지 i번째로 입력을 받은 값이다.
즉, arr[i]의 값을 counting[arr[i]]라는 위치에 넣어주면 된다