백준 #1083 소트(정렬)

이번 문제는 버블 정렬을 잘 이해하고 있다면, 쉽게 풀 수 있는 문제입니다.  난이도가 Gold IV이긴 하지만 더 낮아져도 상관 없을 문제라고 봅니다.   정답비율은 30.5% 정도로 높지가 않습니다.  정답자 184명.

 

https://www.acmicpc.net/problem/1083

1083번: 소트

 

버블 정렬은 이해하기 아주 쉬운 정렬이고, 구현도 쉽게 할 수 있죠.  버블정렬은 이웃한 것끼리 위치를 바꾼다는 개념입니다.  키 순으로 줄을 설 때, 자주 볼 수 있는 모습입니다.

 

bubble sort

 

버블정렬은 이웃한 원소들끼리 서로 교환을 하죠.  버블정렬의 교환횟수는 앞으로 가는 것은 상관없고, 뒤로 가는 것만 카운팅해주면 자연스럽게 해결이 됩니다.  예를 들어서 증가하는 순서로 정렬이 되는 경우,

 

3

5

1

6

2

4

 

이런 배열을 생각해보면, 3은 2칸 오른쪽으로 가야하고, 5는 3칸, 6은 2칸 오른쪽으로 가야합니다.  총 7칸을 오른쪽으로 가야하므로 교환횟수는 7회가 됩니다.

 

3

1

5

6

2

4

3

1

5

2

6

4

3

1

5

2

4

6

5가 한칸 옮겼고, 6이 2칸 옮겨가서 총 3번의 교환이 발생했다.

1

3

5

2

4

6

1

3

2

5

4

6

1

3

2

4

5

6

 3이 한칸 옮겼고, 5가 2칸 옮겨가서 총 3번의 교환이 발생했다.

1

2

3

4

5

6

3이 한칸 옮겨져서 정렬이 완성됐습니다.  결국 오른쪽으로 가야할 숫자들을 계산하면 교환횟수가 정해집니다.

 

이것을 거꾸로 이용하는 것이 바로 이 문제의 핵심입니다.

 

총 교환횟수를 계산하는 것이 아니고, 교환횟수가 제한되어 있습니다.  그리고 가능한 큰 수가 되어야 하고요.  교환횟수가 제한되어 있으므로, 최선의 방법을 찾아야 합니다.

 

1. 첫번째 칸부터 시작합니다.

2. 교환횟수한도내에서 오른쪽에서 가장 큰 수를 찾습니다.

3. 가장 큰 수를 첫번째칸에 옮겨놓고 나머지를 밀어줍니다.  (이작업에서 사실 \(O(N)\) 작업이 발생하므로 다른 알고리즘을 생각해서 바꿀 수 있습니다.  원소가 사라졌다고 단순 마킹하는 것만으로도 OK)

4. 교환횟수를 이동한 숫자만큼 제하고 다음 칸으로 이동후 2번부터 반복합니다.  교환횟수가 0이거나 마지막칸에 도달하면 빠져나옵니다.

 

이것을 바탕으로 짠 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1083 - Sorting
//    - by Aubrey Choi
//    - created at 2019-12-07
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, s, v[50], i, j;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",v+i);
  scanf("%d",&s);
  for(i=0;i<n && s;i++)
  {
    int max=v[i], maxi=i;
    for(j=i+1;j<n && j<=i+s;j++) if(max<v[j]) max=v[j],maxi=j;
    s-=maxi-i;
    while(maxi > i) v[maxi]=v[maxi-1],maxi--;
    v[i]=max;
  }
  for(i=0;i<n;i++) printf("%d ", v[i]); putchar('\n');
}