시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 12507 | 3550 | 2855 | 33.329% |
버블 소트 알고리즘을 다음과 같이 C++로 작성했다.
bool changed = false;
for (int i=1; i<=N+1; i++) {
changed = false; //
for (int j=1; j<=N-i; j++) {
if (A[j] > A[j+1]) {
changed = true;
swap(A[j], A[j+1]);
}
}
if (changed == false) { //이미 정렬이 완료되어 더 이상 swap X
cout << i << '\n';
break;
}
}
위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.
첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.
정답을 출력한다.
5
10
1
5
2
3
3
5
1
3
5
7
9
1
N이 50만이라서 O(N^2)으로 풀면 안됨
정렬 전 index - 정렬 후 index = 이동거리
for문 1번에 이동거리는 1만 이동가능하므로 이동거리를 계산하면 몇 번의 반복이 있었는지 알 수 있음
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
vector<pair<int, int>> A(N); //N개 크기만큼 페어 배열을 저장하기 위한 벡터 생성
for(int i=0; i<N; i++) {
cin >> A[i].first; //맨 처음 배열의 데이터 값을 받음
A[i].second = i; //index 값을 저장
}
sort(A.begin(), A.end()); //A.first을 기준으로 정렬
int MAX = 0;
for(int i = 0; i< N; i++) {
if(MAX < A[i].second - i) //기존 원래의 index - 현재 index = 정렬 전 index - 정렬 후 index
MAX = A[i].second - i; //가장 많이 이동한 값을 저장
}
cout << MAX + 1; //+1은 다 정렬되었을 때도 한 번 for문은 돌아가기 때문
}
출처 - 하루코딩