백준 1377번 버블 소트

문제 링크입니다: https://www.acmicpc.net/problem/1377

버블 소트는 한번 진행될 때마다 각 숫자 좌측으로 한칸씩 이동이 가능하다는 원리를 이용해 푸는 문제였습니다.

알고리즘은 아래와 같습니다.

1. pair<int, int>형 벡터에 숫자와 인덱스를 저장합니다.

2. 숫자를 기준으로 오름차순 정렬을 진행합니다.

3. 해당 숫자에 저장되어있는 인덱스와 정렬 기준 인덱스를 뺀 값이 (좌측으로 이동한 횟수 - 1)입니다.

4. 3에서 구한 값 중 (최대 + 1)을 출력합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N;

        vector<pair<int, int>> v(N);

 

        for (int i = 0; i < N; i++)

        {

                 cin >> v[i].first;

                 v[i].second = i;

        }

 

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

 

        int result = 0;

        for (int i = 0; i < N; i++)

                 result = max(result, v[i].second - i);

 

        cout << result + 1 << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~