1377 - 버블 소트

Problem

Solution

제공해준 버블 정렬 코드로 풀게되면 버블정렬의 시간복잡도로 인해 시간초과가 뜨기에 정렬 전 index 값에서 정렬 후 index 값을 뺀 후 최댓값을 찾은 뒤 더하기 1을 해줘서 풀어야한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  cin.tie(NULL);
  cout.tie(NULL);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<pair<int, int>> A(N);

  for (int i = 0; i < N; i++) {
    cin >> A[i].first;
    A[i].second = i;
  }

  sort(A.begin(), A.end());

  int Max = 0;
  for(int i = 0; i < N; i++) {
    if(Max < A[i].second - i) {
      Max = A[i].second - i;
    }
  }

  cout << Max + 1 << endl;
}
C++
복사