백준 1377 c++ "버블 소트" -PlusUltraCode-

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

[필자 사고]

버블정렬을 떠올려 보자.

버블정렬은 특징은 가장 큰 값이 하나씩 이동하는 형태다.

그러면 사고를 바꿔보자. 이전 인덱스에서 정렬된 인덱스의 차가 결국은 버블정렬이 작동한 횟수다. 

즉 정렬한 뒤의 인덱스와 해당 고유 숫자의 이전 인덱스의차이를 구한 뒤 최대값+1 하는 형태로 구하면 된다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

버블 소트의 정렬 완료 시점 계산

 

이 프로그램은 버블 소트 알고리즘이 몇 번째 회차에서 종료되는지를 계산하는 코드이다.
실제 버블 소트를 수행하지 않고, 정렬 결과만을 이용해 효율적으로 계산한다.

---

코드 전체 구조

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

typedef pair<int, int> Node;
int N;
vector<Node> arr;

int main(void) {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        arr.push_back({ num,i });
    }

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

    vector<int> dist(N, 0);

    for (int i = 0; i < arr.size(); i++) {
        int nowNum = arr[i].first;
        int prevIdx = arr[i].second;
        int nextIdx = i;

        dist.push_back(prevIdx - nextIdx);
    }

    cout << *max_element(dist.begin(), dist.end()) + 1;
}

---

1️⃣ 입력 처리부

cin >> N;
for (int i = 0; i < N; i++) {
    int num;
    cin >> num;
    arr.push_back({ num, i });
}

• N: 입력받은 수열의 길이
• arr: (값, 원래 인덱스) 형태로 저장하는 벡터
  • num: 실제 값
  • i: 입력 당시의 인덱스

이렇게 원래 인덱스를 함께 저장하는 이유는,
정렬 후 “값이 얼마나 이동했는가”를 계산하기 위함이다.

---

2️⃣ 정렬 수행

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

• arr을 값 기준으로 정렬한다.
• 정렬이 끝나면 arr[i]의 second에는 **정렬 전 위치(원래 인덱스)**가 남아 있게 된다.
• 따라서 (원래 인덱스 - 정렬 후 인덱스)를 통해
  각 원소가 몇 칸 앞으로 이동했는지를 계산할 수 있다.

---

3️⃣ 이동 거리 계산

vector<int> dist(N, 0);

for (int i = 0; i < arr.size(); i++) {
    int prevIdx = arr[i].second; // 원래 위치
    int nextIdx = i;             // 정렬 후 위치
    dist.push_back(prevIdx - nextIdx);
}

• 각 원소의 이동 거리를 계산한다.
  • 원래 인덱스(prevIdx)가 크고 현재 인덱스(nextIdx)가 작으면
    그만큼 앞으로 이동한 것이다.
• 이 값이 클수록 버블 소트에서 더 많은 회차가 필요하다.

※ 다만 이 코드에서는 dist(N, 0)을 만든 뒤 push_back()을 사용했기 때문에
실제로는 2N개의 원소가 들어가게 된다.
이 부분은 논리적으로 불필요한 중복이지만, 결과에는 큰 영향을 주지 않는다.

더 깔끔한 구현을 원한다면 push_back() 대신 dist[i] = prevIdx - nextIdx;를 쓰는 것이 좋다.

---

4️⃣ 결과 계산

cout << *max_element(dist.begin(), dist.end()) + 1;

• 가장 많이 앞으로 이동한 원소가 버블 소트에서 가장 오래 걸리는 원소다.
• 버블 정렬의 특성상 이동 거리 + 1이 곧 종료 회차이다.
  (한 회차에 한 칸씩만 앞으로 이동 가능하기 때문)

---

 

예시

입력:

5
10
1
5
2
3

정렬 전:

index : 0  1  2  3  4
value : 10 1  5  2  3

정렬 후:

value : 1  2  3  5 10
index : 1  3  4  2  0

이동 거리 (원래 인덱스 - 정렬 후 인덱스):

1-0 = 1
3-1 = 2
4-2 = 2
2-3 = -1
0-4 = -4

가장 큰 값은 2 → 정답은 2 + 1 = 3

---

 정리

구분 설명

입력 형태	N개의 정수
알고리즘	O(N log N) (정렬 + 한 번의 순회)
핵심 로직	버블 소트에서 각 원소가 이동한 거리의 최댓값 + 1
출력	버블 정렬이 종료되는 회차 수

---

 

---

요약 문장 

버블 정렬은 한 번의 패스마다 큰 수를 한 칸씩 뒤로 밀어낸다.
따라서 실제 정렬이 완료되는 시점은
가장 많이 앞당겨진 원소의 이동 거리 + 1로 계산할 수 있다.
이 로직을 이용하면 버블 정렬을 직접 수행하지 않고
O(N log N)으로 종료 회차를 구할 수 있다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> Node;
int N;
vector<Node> arr;

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back({ num,i });
	}

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

	vector<int> dist(N,0);

	for (int i = 0; i < arr.size(); i++) {
		int nowNum = arr[i].first;
		int prevIdx = arr[i].second;
		int nextIdx = i;

		dist.push_back(prevIdx - nextIdx);
	}

	cout << *max_element(dist.begin(), dist.end()) + 1;
}