문제 번호 6225 --버블 정렬(バブルソート)

6225: 버블 정렬(バブルソート)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 8  해결 문제 수: 4
[제출][채점상황][게시판][:]

문제 설명

번역 : 경남과학고 29기 도회린
오번역이나 문제에 관한 질문은 게시판을 이용해주세요.

버블 정렬(Bubble sort)은 수열을 정렬하는 알고리즘이다. 길이 N의 수열 A를 오름차순으로 정렬하는 예를 들어보자. 버블 정렬은 서로 이웃한 두 수의 대소 관계가 어긋났을 때 두 수의 위치를 교환한다. 이 동작을 수열의 앞쪽부터 차례대로 훑어가며 반복한다. 즉 A(i) > A(i+1)이 되는 곳이 있으면 그 두 수를 교환하고, 이를 i = 1, 2, ..., N-1에 대하여 차례차례 반복한다. 이와 같은 동작을 N-1번 반복하면 수열이 오름차순으로 정렬된다고 알려져 있다.

수열 A의 버블 정렬에 의한 교환 횟수는, 수열 A에 위의 알고리즘을 적용했을 때, 정수의 자리를 바꾸는 횟수를 의미한다. (버블 정렬로 알려진 알고리즘은 루프의 순서나 범위, 종료 조건 등에 따라 사소한 차이가 있을 수 있다. 단 그런 사소한 차이가 있더라도, 같은 수열에 적용했을 때 정수의 교환 횟수에는 차이가 없는 것으로 알려져 있다.)

길이가 N인 수열 A가 주어진다. 수열 A의 임의의 두 정수의 자리를 바꾸어 새로운 수열 A’을 만든다. 이 때, 만들어진 수열 A’를 버블 정렬했을 때, 교환 횟수가 최소한이 되도록 만들려고 한다. A’의 교환 횟수의 최솟값을 구하는 프로그램을 작성하여라. (처음에 교환하는 두 개의 정수는 반드시 이웃하고 있을 필요가 없다는 점에 주의하라.)

입력

첫째 줄에는 수열의 길이 N이 주어진다. N은 1이상, 100,000이하의 정수이다.

이어지는 N개의 줄에는 수열 A의 값들이 주어진다. 각 항의 값은 1이상, 1,000,000,000이하의 정수이다.

출력

수열 A’을 버블 정렬했을 때 교환 횟수의 최솟값을 하나의 정수로 출력하여라.

입력예시

「입력 예시 1」
5
10
3
6
8
1

「입력 예시 2」
5
3
1
7
9
5

「입력 예시 3」
3
1
2
3

출력예시

「출력 예시 1」
0

「출력 예시 2」
2

「출력 예시 3」
1

도움말


예시 1 : 10과 1을 교환하여 수열 A’을 만들면, 그 자체로 정렬되어 있으므로 최소 교환 횟수는 0이다.

예시 2 : 3과 7을 교환하여 수열 A’ (3, 1, 5, 9, 7)을 만들면, 버블 정렬을 실행했을 때 교환 횟수가 2이다. 다른 방식으로 2보다 작은 교환 횟수를 가진 수열 A’를 만들 수 없으므로 최소 교환 횟수는 2이다.

예시 3 : 수열 A는 이미 정렬되어 있지만, 새로운 수열 A’을 만들면 다시 정렬해야한다. 이 때 최소 교환 횟수는 1이다.

출처

JOI 2012/2013 본선 

[제출][채점상황]