https://www.acmicpc.net/problem/1377
#include <iostream>
using namespace std;
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main()
{
int N;
cin >> N;
int* A = new int[N];
for (int k = 1; k < N+1; k++) {
cin >> A[k];
}
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;
}
}
return 0;
}
정직하게 버블 정렬을 활용해서 해결하니까 시간 초과가 떠버렸다,,
아무래도 다른 방식으로 접근해야될 것 같다,,
예를 들어서, 입력 값이 10 1 5 2 3 이라고 치면

{
int n;
cin >> n;
vector<pair<int, int>> v;
int val;
for (int idx = 0; idx < n; idx++) {
cin >> val;
v.push_back(pair<int, int>(val,idx));
}
sort(v.begin(), v.end());
int r = 0;
for (int i = 0; i < n; i++) {
if (v[i].second - i > r) {
r = v[i].second - i;
}
}
cout << r + 1 << '\n';
return 0;
}
❗ vector<pair<int,int>> v(n) 은 n개의 값이 모두 0으로 초기화됨 주의
보기에 쉬워서 만만하게 봤다가 시간 초과가 떠서 정말 당황했다...😱
하긴 이렇게 쉬울리가 없지,, 초반에 버블 정렬에 제대로 꽂혀버려서 다른 접근 방식을 생각해내기 힘들었다,,ㅎㅎ
그리고 알고리즘을 구현하는 것은 쉬웠지만 c++에 익숙하지 않아서 소스 코드로 구현하는데 힘들었다.