2750번

수도 코드

N (정렬할 수 개수)
A (수 저장 배열)

for(i-> 0이상 N-1미만):
	for(j-> 0이상 N-1-i미만):
    	현재 배열 A값보다 한 칸 오른쪽 배열값이 더 작으면 swap

배열 A 출력

답안

#include <iostream>
#include <vector>

using namespace std;

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

  cin >> N;
  vector<int> A(N, 0);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  
  for (int j = N - 1; j >= 1; j--) {
    bool isSwapOccured = false;
    for (int i = 0; i < j; i++) {
      if (A[i] > A[i + 1]) {
        isSwapOccured = true;
        int temp = A[i];
        A[i] = A[i + 1];
        A[i + 1] = temp;
      }
    }
    if(!isSwapOccured) break;
  }
  for (int i = 0; i < N; i++) {
    cout << A[i] << "\n";
  }
}

1377번

아이디어

• 정렬된 숫자가 우측에 쌓이는 구조의 버블정렬인 경우, 안쪽 루프에서 swap시 좌측으로 이동될 수 있는 거리는 최대 1이다.
  반대로 정렬된 숫자가 좌측에 쌓이는 구조의 버블정렬이라면 우측으로 최대 1씩 이동할 수 있다.

• 자기 자리를 찾아가는 수는 반복 때마다 끊임없이 이동한다.
  예를 들어 오름차순 정렬할 때 1이라는 숫자가 마지막에 있다면, 매 반복때마다 좌측으로 1칸씩 이동한다.

• 따라서 왼쪽으로 제일 많이 이동한 거리를 구하면 해결 할 수 있다.
  다만, swap되지 않은 마지막 반복(정렬이 끝난상태)일 때도 count해야 하므로 +1 해야함을 잊지말자.

수도 코드

N (데이터 개수)
A (데이터 저장 배열)

for(N만큼 반복):
	A 저장
    
배열 A 정렬

for(N만큼 반복):
	배열 데이터 정렬 전 index - 정렬 후 index 계산 값의 최대값을 찾아 저장
    
최대값 +1을 정답으로 출력

답안

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

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

  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;
}