백준 1337: 버블 소트

 

📃 문제: 백준 1377(버블소트)

1377번: 버블 소트

버블 소트 알고리즘을 다음과 같이 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]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

 

 

🥈 난이도: 실버 1

 

 

😲 사용한 개념: 버블소트에 대한 이해, vector<pair<자료형, 자료형>> 사용

 

☝️ 문제에서 주어진 버블소트 코드를 보면, 내부 for문 안에서 swap이 한번도 일어나지 않은 경우 (changed=false)

프로그램을 종료한다.

내부 for문을 한바퀴 순회할 동안 swap이 한번도 일어나지 않았다는 이야기는, 모든 원소가 이미 정렬 완료된 상태라는 이야기로, 불필요한 추가 비교 연산을 수행하지 않기 위한 최적화 플래그 값이라고 생각하면 된다.

 

✌️ 문제 풀이시 이용한 vector <pair<int, int>> A에서 sort함수를 적용시, 정렬은 A[i].first를 기준으로 한다.

만약  A[i].first 비교시, 값이 같은 원소의 경우에만 A[i].second를 기준으로 비교하여 정렬한다.

 

 

 

📖 풀이 사고 과정

 

 

 

👩‍💻 구현 코드(c++ 사용)

 

    💛 vector pair를 사용해  시간복잡도를 개선한 코드 (find함수 제거)

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

int main(void) {
    ios::sync_with_stdio;
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<pair<int, int>> arr(N);
    //arr[i].first에 value, arr[i].second에 index 저장
    for (int i = 0; i < N; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
    //sort()함수 -> 기본적으로 arr.first값을 기준으로 정렬(->같을 경우 arr.second값 기준으로 정렬)
    int max = 0;
    sort(arr.begin(), arr.end());
    for (int i = 0; i < N; i++) {
        if (max < arr[i].second - i) max = arr[i].second - i;
    }
    cout << max+1;
    return 0;
}

 

 

 

    👿 for문 안에 find 함수를 사용해 시간초과가 난 코드 => 시간복잡도 O(n*n)

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

int main(void){
    ios::sync_with_stdio;
    cin.tie(NULL);
    cout.tie(NULL);
    int N, num;
    vector<int> arr, original_arr, original_index;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num;
        arr.push_back(num);
        original_arr.push_back(num);
    }
    sort(arr.begin(), arr.end());

    for (int i = 0; i < N; i++) {
        // vector내에서 해당 원소가 위치하는 인덱스 찾기
        //find(v.begin(), v.end(), 찾을 대상) - v.begin()
        original_index.push_back(find(original_arr.begin(), original_arr.end(),arr[i]) - original_arr.begin());
    }
    int max = 0;
    for (int i = 0; i < N; i++) {
        if (original_index[i] - i > max) {
            max = original_index[i] - i;
        }
    }
    cout << max + 1 << endl;
    return 0;
    }