Tutorial : STL Reverse timer 2s memory 1024MB

앞선 STL Sort 정렬 기준 설정 문제 에서 우리는 원하는 대로 정렬 기준을 설정할 수 있었다.

이를 이용하면 내림차순 정렬은 쉽게 구현할 수 있다.

bool comp(int Left, int Right){
    return Left > Right;
}

int main(){
    int A[5] = {1, 2, 3, 4, 5};
    sort(A+0, A+5, comp);
}

배열에서 오른쪽으로 갈수록 숫자가 작아져야 하기 때문에, 왼쪽 숫자(Left) 보다 오른쪽 숫자(Right) 가 작도록 comp 를 짜면 된다.

약간의 발상의 전환을 하면 이렇게도 생각할 수 있다.

"오름차순으로 정렬해놓고, 배열 전체를 뒤집으면 되지 않을까?"

이것 또한 정답이다. 따라서 이번에는 배열의 원하는 구간을 뒤집는 reverse 함수를 배울 것이다.

reverse 함수는 사용법이 sort 함수와 완전히 동일하다.

배열 A 의 s 번 칸부터 e 번 칸까지를 뒤집고 싶다면, 아래 코드를 짜주면 된다.

reverse ( A + s , A + e + 1 );

reverse 함수도 sort 와 마찬가지로 #include <algorithm> 헤더에 있고, using namespace std; 를 해줘야 한다.

배열 A의 모습이 위와 같다. 여기에 아래 코드를 적용하면,

reverse ( A + 1 , A + 5 );

A[1] ~ A[4] 가 뒤집히고, 배열 A는 아래와 같이 변한다.

시간복잡도는 당연히 O( 뒤집히는 구간의 길이 ) 가 된다.