[백준] 정렬(1083)

문제 링크 : [백준] 정렬(1083)

문제 설명

배열이 주어졌을 때, 인접한 두 수를 교환하는 행위를 최대 M번 행하여 만들 수 있는 배열 중, 사전순으로 가장 나중에 오는 배열을 출력하세요.

입력

N(배열의 크기, 1 <= N <= 50)
A_i(배열 각각의 값, 1 <= A_i <= 1,000,000)
M(최대 교환 횟수, 1<= M <= 1,000,000)

7
10 20 30 40 50 60 70
1

출력

20 10 30 40 50 60 70

카테고리

#그리디

시간 복잡도 상한

엄청 커도 됩니다.

해결 방법

1. 처음에는 버블소트의 개념으로 앞에서부터 뒤의 숫자보다 작은 경우, 반복해서 수를 교환하는 방법을 사용했습니다.
2. 그래서 엄청 틀렸습니다.
3. 그리디라는 풀이 방법은 맞으나 풀이 방법이 틀렸습니다.
4. 앞에서부터 반복적으로 교환을 하게 되면, 가장 큰 값이 뒤쪽에 있는 경우, 틀린 답이 나올 수 있습니다.
   4-1. 예시) 1 2 3 4 5, M이 4인 경우,
   4-2. 제 풀이 방법으로는 2 1 3 4 5, 2 3 1 4 5, 3 2 1 4 5, 3 2 4 1 5가 나옵니다.
   4-3. 하지만 답은, 5 1 2 3 4 가 됩니다.
5. 문제는 이동방법을 잘 못 결정하였습니다.
6. 맨 왼쪽 위치부터 내가 이동할 수 있는 범위 내에서 최댓값을 기준 위치로 이동시키고, 이동한 만큼 M값을 감소시킵니다.
   6-1. 최댓값을 현재 인덱스로 이동시키는데 그만큼 값을 썼기 때문입니다.
7. 6에서 기준이 된 인덱스의 다음 인덱스에서 6을 다시 실행합니다.
8. 6,7을 반복하면서 M이 0이 되는 순간 break를 걸고 값을 출력합니다.
9. M이 엄청 큰 경우 TLE가 날 것 같으나, 실제로 최악의 경우에 O(N²)의 시간복잡도를 가집니다.

시간복잡도

O(N²)

코드

#include<cstdio>
int n,m,d[50],i,j,x,y,t;
int main(){
    scanf("%d",&n);
    for(;i<n;i++)scanf("%d",d+i);
    scanf("%d",&m);
    for(i=0;i<n;i++){
        for(x=0,j=i;j<n&&j-i<=m;j++)if(x<d[j])x=d[j],y=j;
        for(m-=(y-i);i<y;y--)t=d[y],d[y]=d[y-1],d[y-1]=t;
    }
    for(i=0;i<n;i++)printf("%d ",d[i]);
}