[백준/C++] 1377번: 버블 소트

📁 문제

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

💭 첫 번째 풀이 (시간 초과)

#include <iostream>
using namespace std;

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main()
{
	int N;
	cin >> N;

	int* A = new int[N];

	for (int k = 1; k < N+1; k++) {
			cin >> A[k];
	}

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

정직하게 버블 정렬을 활용해서 해결하니까 시간 초과가 떠버렸다,,
아무래도 다른 방식으로 접근해야될 것 같다,,

예를 들어서, 입력 값이 10 1 5 2 3 이라고 치면

![예시](
그리고 3단계에서는 이동이 없으므로 버블 정렬은 3단계에서 끝난다.

따라서 좌측으로 밀려나는 값이 좌측으로 몇 번 밀려났는지 알면 버블 정렬 횟수를 알 수 있다.

즉, 좌측으로 가장 많이 밀려난 횟수가 버블 정렬이 일어난 횟수가 된다.

1. 정렬 전과 정렬 후의 인덱스를 비교한다.
   • 정렬 후 인덱스 값에서 정렬 전 인덱스 값을 뺀 값이
   • 양수이면 좌측으로 이동, 음수이면 우측으로 이동
2. 정렬 후 인덱스 값에서 정렬전 인덱스 값을 뺀 값 중, 가장 큰 값 + 1을 하면 된다.

vector와 pair를 사용하여 문제를 해결하였다.

• 정렬 전 인덱스와 입력 값을 쌍으로 저장

🤍 성공!

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

int main()
{
    int n;
    cin >> n;

    vector<pair<int, int>> v;
    int val;

    for (int idx = 0; idx < n; idx++) {
        cin >> val;
        v.push_back(pair<int, int>(val,idx));
    }

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

    int r = 0;
    for (int i = 0; i < n; i++) {
        if (v[i].second - i > r) {
            r = v[i].second - i;
        }
    }
    
    cout << r + 1 << '\n';

    return 0;
}

❗ vector<pair<int,int>> v(n) 은 n개의 값이 모두 0으로 초기화됨 주의

보기에 쉬워서 만만하게 봤다가 시간 초과가 떠서 정말 당황했다...😱
하긴 이렇게 쉬울리가 없지,, 초반에 버블 정렬에 제대로 꽂혀버려서 다른 접근 방식을 생각해내기 힘들었다,,ㅎㅎ
그리고 알고리즘을 구현하는 것은 쉬웠지만 c++에 익숙하지 않아서 소스 코드로 구현하는데 힘들었다.

📚 참고한 블로그

• vector 사용법 - https://blockdmask.tistory.com/70
• pair 사용법 - https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=chansung0602&logNo=221006857783
• vector와 pair 사용
  • https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ckdgus1433&logNo=221666899817
  • https://godog.tistory.com/entry/c-vector-and-pair-%EC%82%AC%EC%9A%A9