문제 링크 http://icpc.me/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 개인적으로 알고 나면 쉽지만 아이디어가 많이 어려운 문제인 것 같다. 문제를 잘 관찰을 해본다면 출력을 하는 수는 정렬이 끝난 다음 시점의 i값이다. 편의상 인덱스가 작은 방향을 왼쪽, 큰 방향을 오른쪽이라 하겠다. 정렬이 모두 끝난 시점을 알기 위해서는 왼쪽으로 밀려난 수 중 가장 많이 밀려난 수가 몇 번 왼쪽으로 밀려났는지를 알면 된다. 그 이유는 왼쪽으로 가야 하는 어떤 수는 한번 ..