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]가 왼쪽으로 이동한 횟수)가 되며 이는 정렬 한 번으로 구할 수 있다.
끝
'일기' 카테고리의 다른 글
| 2023년 5월 30일 일기 (6) | 2023.05.30 |
|---|---|
| BOJ 28039번 - 카드 게임 2 (0) | 2023.05.25 |
| 2023 우아한테크캠프 6기 1차 코딩테스트 (0) | 2023.05.09 |
| Ghudegy 정품 키 (0) | 2023.04.30 |
| 자담치킨 신메뉴 티키타코 순살치킨 후기 (2) | 2023.04.28 |
