일기
BOJ 1377번 - 버블 소트
hijkl2e
2023. 5. 17. 12:25
1377번: 버블 소트
첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.
www.acmicpc.net
매 루프에서 어떠한 원소 A[i]의 상태는 다음 중 하나이다.
- 왼쪽으로 1칸 이동한다.
- 오른쪽으로 x칸 이동한다.
- 이동하지 않는다.
그리고 상태 전이는 항상 이 순서대로 이루어진다.
예를 들어 오른쪽으로 이동하다가 왼쪽으로 이동하는 일은 발생하지 않는다는 것이다.
오른쪽으로 이동하는 원소가 있다면 왼쪽으로 이동하는 원소도 반드시 존재함에 주목하자.
따라서 답은 max(A[i]가 왼쪽으로 이동한 횟수)가 되며 이는 정렬 한 번으로 구할 수 있다.
끝