[ C++ / 정렬 ] 백준 1377 - 버블 소트

Minsu._.Lighting·2023년 11월 10일

🔗 자료구조 / 알고리즘

목록 보기

3/9

📄 문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.
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;
   }
}
위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

⌨ 입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

💻 출력

정답을 출력한다.

📌 예제

[ Input ]

5
10
1
5
2
3

[ Output ]

3

📝 풀이

핵심

정렬이 총 몇번 일어났는지 찾아내는 문제

버블 정렬(지문 예시 코드)사용 시 시간 복잡도에 의해 시간 초과 발생

원소 중 가장 많이 이동한 값 + 1 == 버블 정렬 횟수
📌스왑이 일어나지 않는 for문이 한번 더 실행되기 때문에 + 1 적용

소스 코드

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

using namespace std;

int iN = 0;

vector<pair<int, int>> vecBefore;
vector<pair<int, int>> vecAfter;

int iAnswer = 0;

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

    cin >> iN;

    for (int i = 0; i < iN; ++i)
    {
        int iNumber = 0;

        cin >> iNumber;
        
        vecBefore.emplace_back(iNumber, i);
        vecAfter.emplace_back(iNumber, i);
    }

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

    for (int i = 0; i < iN; ++i)
    {
        int iA = vecAfter[i].second - vecBefore[i].second;

        if (iAnswer <= iA)
        {
            iAnswer = iA + 1;
        }
    }

    cout << iAnswer;

    return 0;
}