BOJ 1083 소트

 

문제 링크 : https://www.acmicpc.net/problem/1083

1083번: 소트

 

가장 앞자리부터 가능한한 큰 수로 교환하고,

교환 횟수가 남아있다면 그 다음 자리로 가서 이를 반복한다.

 

알고리즘은 더 설명할 게 없고,

아래 코드에서 algorithm 라이브러리에 있는 rotate 함수를 설명하면 충분할 듯하다.

 

rotate( arr+start , arr+p , arr+end );

arr 이 배열인 경우 [ start , end ) 에 존재하는 원소들을 p 에 위치한 것이 가장 앞에 올 때까지

왼쪽으로 이동시킨다. (물론 선두인 start 위치의 것은 end-1로 보낸다.)

 

다음과 같은 알고리즘으로 구현되어 있다고 한다.

 

template <class ForwardIterator>
  void rotate (ForwardIterator first, ForwardIterator middle,
               ForwardIterator last)
{
  ForwardIterator next = middle;
  while (first!=next)
  {
    swap (*first++,*next++);
    if (next==last) next=middle;
    else if (first==middle) middle=next;
  }
}

 

(정말 구현이 위와 같이 된 것은 아니고 위의 코드와 동등하다고 설명되어 있다.)

어쨌든 이 코드는 이해하기 쉽지 않다.

더우기 정말 배열의 원소들의 값을 교환하고 있어서 효율이 좋아 보이지도 않는다.

 

원래는 모듈러(modular) 연산을 이용하여 rotate 함수와 같은 결과를 만드는 함수를 작성해서 풀었지만...

코드가 못생겨져서 그냥 rotate 함수를 사용했다.