Hoon222y

https://www.acmicpc.net/problem/1377 버블 소트가 총 몇 회 발생하는지 찾는 문제이다. 하지만 그냥 실제로 버블 소트를 하면서 버블 소트 횟수를 찾게되면 N의 제한이 50만이고 복잡도가 O(N^2)이므로 시간초과이다. 이 문제의 경우 버블 소트의 특성을 잘 이해하면 풀 수 있는 문제이다. 버블 소트의 경우 한번 반복될 때 오른쪽으로는 몇번을 이동하게 되던, 왼쪽으로는 어떤 수이던 딱 한번만 움직이게 된다. 따라서 처음 입력에서 sort한 이후에 인덱스의 차이가 가장 큰 경우를 찾아주면 되는 문제이다. 12345678910111213141516171819202122232425262728293031323334#include #include #include #include #inc..