5531번 - 버블 정렬 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 448 | 62 | 45 | 16.187% |
문제
버블 정렬은 다음과 같은 의사 코드를 가지는 가장 간단한 정렬 방법 중 하나이다.
void bubble_sort(int *a, int n) {
int i, j;
for (i = 0; i < n - 1; ++i) {
for (j = 0; j < n - 1; ++j) {
if (a[j] > a[j + 1]) {
/* 순서가 틀린 쌍이라면, 두 쌍을 교환한다. */
/* 이때 두 쌍의 교환 횟수는 1 증가한다. */
int x = a[j];
a[j] = a[j + 1];
a[j + 1] = x;
}
}
}
}
길이 n인 배열 A에 대해서 A*를 정의하고자 한다. A*는 배열 A의 i번째 원소와 j번째 원소를 한번만 바꿔놓은 배열이다. (1 ≤ i < j ≤ n).
모든 배열 A* 중, 교환 횟수가 최소인 배열 A*의 교환 횟수를 출력하라.
입력
첫 번째 줄에 정수 N이 주어지며, 이후 N개의 줄에 배열 A가 A1, ..., AN 순서로 주어진다.
출력
배열 A* 중 교환 횟수가 최소인 배열의 교환 횟수를 출력한다.
제한
- 1 ≤ N ≤ 100,000
- 1 ≤ Ai ≤ 1,000,000,000
예제 입력 1
5 10 3 6 8 1
예제 출력 1
0
1과 10을 바꾸면 {1,3,6,8,10} 으로 정렬된 형태가 완성되기에 최솟값은 0이다.
예제 입력 2
5 3 1 7 9 5
예제 출력 2
2
예제 입력 3
3 1 2 3
예제 출력 3
1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호