1377 버블 소트

다음 과 같은 소스의 결과를 출력하는 문제이다.
바보같이 저대로 입력해서 제출하면 바로 TLE를 맛보게 된다.
즉, 저 소스의 결과를 유지하면서, 연산은 최소화 해야한다.

어떤 규칙이 있을까? 가장 눈에 보이는것은 1부터 시작해서 n-1까지 계속 스왑을 해주는것이다. 변화가 없을때 까지 반복한다는것은, 가장 변화를 늦추게 하는 숫자를 찾으면 되지않는가! 그리고 그 변화를 늦추는것은 정렬 위치상 앞에 있는 숫자가, 뒤에 있는 경우이다. 그 간격이 가장 큰 것이 변화를 가장 늦추는 숫자이다.

따라서 이 문제를 풀기위해선 같은 값을 저장하는 배열a,b를 저장하고, a는 빠른 정렬함수를 이용해 정렬을 해준다.
그리고 b의 처음 숫자부터 시작해서 a에 같은 숫자가 있는지를 이진탐색을 통해 찾아준다.(반드시 있어야 한다)
찾으면 처음 숫자의 인덱스 - a에서 찾은 숫자의 인덱스 의 최대값을 구하면 된다.
여기서 문제는, 이진탐색으로 찾게 되면 중복된 숫자가 있을 때 값이달라져 버린다. 이 때는 중복된 숫자의 위치상 상한을 찾아서 그것과 비교하도록 처리해주어야 한다. 매번 검색해주면 TLE가 생기니 한번 검색해준것은 저장하여 다음엔 바로 넘어가도록 해주자.

소스