[백준] 1377번: 버블 소트

---

🔗 문제 링크

https://www.acmicpc.net/problem/1377

---

반응형

728x90

👩‍💻 코드

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    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;
    
    return 0;
}

---

📝 풀이

Do it! 알고리즘 코딩테스 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

 

버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제입니다.

버블 정렬의 swqp이 한 번도 일어나지 않았다는 것은 이미 모든 데이터가 정렬됐다는 것을 의미합니다.

하지만 버블 정렬로 문제를 풀면 시간 초과가 일어날 수 있기 때문에 다른 아이디어가 필요합니다.

 

버블 정렬의 안 쪽 루프는 1에서 N-i까지 왼쪽에서 오른쪽으로 이동하며 swap을 수행합니다.

이는 특정 데이터가 안쪽 루프에서 swqp의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻입니다.

즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 됩니다.

 

정렬 전 데이터를 (값, 인덱스)로 A에 저장합니다.

sort 함수를 통해 정렬을 수행한 후 정렬 전 index와 정렬 후 index 차를 구합니다.

이 중 가장 큰 값을 찾고 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 1을 더하여 출력합니다.