https://www.acmicpc.net/problem/1377
문제
- N은 500,000보다 작거나 같은 자연수
- 아래와 같은 코드를 실행 시켰을때 출력되는 숫자는?
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) {
cout << i << '\n';
break;
}
}
-> 시간제한 = 2초, 위 코드의 시간 복잡도 = O(N^2) 이므로 당연한(?) 얘기지만 그냥 구현은 안된다.
간단히 알아보는 정렬 방법
더보기
1. 버블 정렬 (Bubble Sort)
- 방법: 리스트가 정렬될 때까지 반복하며, 인접한 두 원소를 비교하여 필요하면 자리를 바꾼다.
- 시간 복잡도:
- 최악: O(n^2)
- 최선: O(n)(정렬된 경우)
- 평균: O(n^2)
2. 선택 정렬 (Selection Sort)
- 방법: 매번 최솟값을 찾아 현재 위치와 교환.
- 시간 복잡도:
- 최악: O(n^2)
- 최선: O(n^2)
- 평균: O(n^2)
3. 삽입 정렬 (Insertion Sort)
- 방법: 현재 요소를 적절한 위치에 삽입하여 부분 배열을 정렬 상태로 유지.
- 시간 복잡도:
- 최악: O(n^2)
- 최선: (정렬된 경우)
- 평균: O(n^2)
4. 병합 정렬 (Merge Sort)
- 방법: 배열을 반으로 나눈 후 각각 정렬하고 합친다.
- 시간 복잡도: (모든 경우)
5. 퀵 정렬 (Quick Sort)
- 방법: 피벗을 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값으로 분할 정렬합니다.
- 시간 복잡도:
- 최악: O(n^2) (이미 정렬된 경우)
- 평균:
참고로 C++에서 <algorithm> 헤더에 있는 sort()함수는 기본적으로 퀵 정렬 + 삽입 정렬 식으로 섞여서 구현되어있다.
따라서 시간 복잡도 : O(nlogn)을 보장한다!
아이디어
- nlogn으로 정렬을 해야함.
- 기존 버블 정렬의 순서를 따로 기억할 인덱싱을 놔둠.
문제 풀이
- 결국 버블 정렬에서 바깥 for문이 몇 번 돌고 정렬이 종료되었냐 이므로, 원래 위치 -> 정렬 이후 위치가 가장 큰값 = 최종 반복 횟수!
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
// 숫자, 인덱스
vector<pair<int, int> > arr(500001);
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
}
// 오름차순 정렬하면서 총 반복 횟수
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
arr[i] = {a, i};
}
sort(arr.begin() + 1, arr.begin() + n + 1, cmp);
int res = -1;
for (int i = 1; i <= n; i++) {
// (원래 인덱스 - 정렬 이후 인덱스)의 최댓값 -> 몇 번 반복인지 알기 위해
if (res < arr[i].second - i) res = arr[i].second - i;
}
cout << res + 1;
}트러블 슈팅
사실 접근 방법은 맞았지만 뭐가 문젠지 계속 실패했다...
이 부분은 검색을 통해서 알아내긴 했지만, C++에서 제공하는 sort()는 불안정 정렬(unstable sort)이라는 점이다.
불안정 정렬?
배열 : [2, 1, 5, 4(처음 나오는 4), 4(두번째 나오는 4), 3, 6]
위 배열에서 기존 sort()를 이용한다면 두개의 4는 처음 나오는 4인지 두번째 나오는 4인지 알 수도 없고, 보장해주지도 않는다!
그렇다면? 아래와 같은 방법이 있다.
- table_sort() 이라는 병합 정렬을 사용
- 비교함수 커스터마이징
나는 비교함수에 조건을 추가하여 커스터마이징 해줬다.
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
}여기서 바로 if 부분이다. 이렇게 되면 같은 숫자가 들어와도 기존 인덱스 순서를 해치지 않고 정확한 인덱스의 이동거리를 알 수 있다!!
