[ 백준 / C ] 1015번 : 수열 정렬

1015

#include <stdio.h>

int main(void){
    // 배열 길이 입력
    int length;
    scanf("%d", &length);

    int max =0;
    int P_arr[length], B_arr[length];

    for(int i = 0; i < length; i++){
        // 원소 입력 받기
        int num;
        scanf("%d", &num);

        B_arr[i] = num;
        P_arr[i] = i;
        int t = i; // 현재 입력 받은 값의 위치

        // 비내림차순 정렬
        // i-1부터 0까지 비교할것
        for(int j = i-1; j >= 0; j--){
            // t번째의 값이 j번째 값보다작으면 swap
            if(B_arr[j] > B_arr[t]){
                // swap
                int tmp_B = B_arr[j];
                B_arr[j] = B_arr[t];
                B_arr[t] = tmp_B;

                // B[P[k]] = A[k]를 이용하여
                // 값이 j인 P[k]의 k 구하기
                int k = 0;
                for(; k < i; k++){
                    if(P_arr[k] == j){
                        break;
                    }
                }

                // P[i] 와 P[k] swap
                int tmp_P = P_arr[k];
                P_arr[k] = P_arr[i];
                P_arr[i] = tmp_P;

                // 현재 입력 받은 값의 위치 저장
                t = j;
            }
        }
    }

    // 출력
    for(int i = 0; i < length; i++){
        printf("%d ", P_arr[i]);
    }
    return 0;
}

아래는 내가 이해를 위해서 메모장에 표기한거임 참고

길이 N = 4
배열 A ={2 1 3 1}

@@@@@@@@@@@@
i = 0
t = 0
B[0] = 2

P[0] = 0

@@@@@@@@@@@@
i = 1
t = 1
B[0] = 2
B[1] = 1

P[1] = 1
~~~~~~~~~~~~~~~~~
B[0] = 1
B[1] = 2

P[0] = 1
P[1] = 0
t = 0
@@@@@@@@@@@@
i = 2 
t = 2
B[0] = 1
B[1] = 2
B[2] = 3

P[2] = 2

P[0] = 1
P[1] = 0
P[2] = 2

@@@@@@@@@@@@
i = 3
t = 3
B[0] = 1
B[1] = 2
B[2] = 3
B[3] = 1

P[3] = 3
~~~~~~~~~~~~~~~~~
B[0] = 1
B[1] = 2
B[2] = 1
B[3] = 3

P[2] = 3
P[3] = 2
t = 2
~~~~~~~~~~~~~~~~~
B[0] = 1
B[1] = 1
B[2] = 2
B[3] = 3

P[0] = 2
P[1] = 0
P[2] = 3
P[3] = 1
t = 1
@@@@@@@@@@@@

B[P[0]=2] = (A[0]=2)
B[P[1]=0] = (A[1]=1)
B[P[2]=3] = (A[2]=3)
B[P[3]=1] = (A[3]=1)

실버4 문제였는데,,, 푸는데 시간을 넘 많이 씀,, 코드도 막 깨끗하진 않음... 슬프다...ㅜㅜ

근데 저 문제에 예제 좀 더 필요할거 같음

처음 풀었을때 예제에 있는거 다 맞았는데 틀렸다고 해서 반례 계속 찾았더니 반례가 있었음

 

---

이거 덕분에 반례 찾았음요!!

내 코드는

5
1 2 1 2 1
일때

0 4 1 3 2가 나오는거임

0 3 1 4 2가 나와야함ㅇㅇ

#include <stdio.h>

int main(void){
    int length;
    scanf("%d", &length);

    int max =0;
    int P_arr[length], B_arr[length];

    for(int i = 0; i < length; i++){
        int num;
        scanf("%d", &num);

        B_arr[i] = num;
        P_arr[i] = i;
        int p = i;
        for(int j = 0; j < i; j++){
            if(B_arr[j] > B_arr[i]){
                int tmp_B = B_arr[j];
                B_arr[j] = B_arr[i];
                B_arr[i] = tmp_B;

                int k = 0;
                for(; k < i; k++){
                    if(P_arr[k] == j){
                        break;
                    }
                }
                int tmp_P = P_arr[k];
                P_arr[k] = P_arr[p];
                P_arr[p] = tmp_P;

                p = k;
            }
        }
    }

    for(int i = 0; i < length; i++){
        printf("%d ", P_arr[i]);
    }
    return 0;
}

0 4 1 3 2 코드는 위의코드였는데 

i번째와 0~i-1번째 까지 비교하는 방식이여서 사전순을 만족 못함 

ex) 

B = 1 1 2 2 1

P = 0 2 1 3 4

B[P[0] =0] = A[0] = 1

B[P[2] =1] = A[2] = 1

B[P[1] =2] = A[1] = 2

B[P[3] =3] = A[3] = 2

B[P[4] =4] = A[4] = 1

 

B = 1 1 1 2 2

P = 0 4 1 3 2

B[P[0] =0] = A[0] = 1

B[P[2] =1] = A[2] = 1
B[P[4] =2] = A[4] = 1

B[P[3] =3] = A[3] = 2

B[P[1] =4] = A[1] = 2
이케 되는거ㅋㅋ 어지럽긴한데 ㅇㅇ 이해완? ㅋㅋ ㅜㅜ

 

0 3 1 4 2 코드는 맨 처음코드임
현재 입력받은 값의 위치와 i-1~0번째 까지 비교함 그래서 사전순을 만족함

ex) 

B = 1 1 2 2 1

P = 0 2 1 3 4

B[P[0] =0] = A[0] = 1

B[P[2] =1] = A[2] = 1

B[P[1] =2] = A[1] = 2

B[P[3] =3] = A[3] = 2

B[P[4] =4] = A[4] = 1

 

B = 1 1 1 2 2

P = 0 3 1 4 2

B[P[0] =0] = A[0] = 1

B[P[2] =1] = A[2] = 1
B[P[4] =2] = A[4] = 1

B[P[3] =4] = A[3] = 2

B[P[1] =3] = A[1] = 2

긍께 걍 뒤에서 부터 비교함....

---

아니 .... 다른 사람 코드 찾아봤는데 왜케 짧고 간단해???????
이게 실력차이???? ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ