백준 1377 버블정렬 c++ // 버블정렬 필요 사이클 구하기

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

 

• 버블정렬이 완료될때까지 몇 사이클이 필요한지 구하는 문제.

 

 

1. 버블 정렬의 동작 방식

예제: [10, 1, 5, 2, 3]

첫 번째 패스:
[10, 1, 5, 2, 3] -> [1, 10, 5, 2, 3] -> [1, 5, 10, 2, 3] -> [1, 5, 2, 10, 3] -> [1, 5, 2, 3, 10]
(10이 한 패스에서 한 칸씩 오른쪽으로 이동)

두 번째 패스:
[1, 5, 2, 3, 10] -> [1, 2, 5, 3, 10] -> [1, 2, 3, 5, 10]
(5가 제자리로 이동)

세 번째 패스:
[1, 2, 3, 5, 10]
(변화 없음, 정렬 완료)

2. 핵심 아이디어

• 각 숫자가 "최종 위치"까지 가는데 필요한 왼쪽으로의 이동 횟수를 찾습니다.
• 왜냐하면 버블 정렬에서 한 패스당 숫자는 최대 1칸씩만 이동할 수 있기 때문입니다.
• 버블정렬이 우측으로 옮기는 특성을 이용!!
• 우측으로 얼마만큼 갔는지 ==  몇번 사이클이 돌았는지 와 같음.
• 정렬전 idx - 정렬후 idx중 최대값 +1이 정답!

예제에서 각 숫자의 이동:

입력:
5
10 1 5 2 3

과정:
1. 원래 위치와 함께 저장: 
   (10,0) (1,1) (5,2) (2,3) (3,4)

2. 정렬 후:
   (1,1) (2,3) (3,4) (5,2) (10,0)
   idx 0   1      2    3     4
    1      2      2   -1   -4 //정렬전 idx - 정렬후 idx

3. 각 원소의 이동:
   1: 1 -> 0  (왼쪽으로 1칸)
   2: 3 -> 1  (왼쪽으로 2칸)
   3: 4 -> 2  (왼쪽으로 2칸)
   5: 2 -> 3  (오른쪽으로 1칸)
   10: 0 -> 4 (오른쪽으로 4칸)

4. 최대 이동 거리: 2
   답: 2 + 1 = 3

3. 코드 설명

// 1. 원래 위치 기록
vector<pair<int,int>> withIdx;
for(int i = 0; i < n; i++) {
    withIdx.push_back({arr[i], i});  // {값, 원래 인덱스}
}

// 2. 값 기준으로 정렬
sort(withIdx.begin(), withIdx.end());

// 3. 각 숫자가 왼쪽으로 얼마나 이동했는지 확인
int maxMove = 0;
for(int i = 0; i < n; i++) {
    // withIdx[i].second = 원래 위치
    // i = 정렬 후 위치
    // 둘의 차이 = 이동 거리
    if(withIdx[i].second - i > maxMove) {
        maxMove = withIdx[i].second - i;
    }
}

// 4. 최대 이동 거리 + 1이 답
return maxMove + 1;

왜 maxMove + 1이 답인가?

1. 버블 정렬은 한 패스에서 각 원소를 최대 1칸씩만 이동시킬 수 있음
2. 어떤 원소가 x칸 이동해야 한다면, 최소 x번의 패스가 필요
3. 마지막으로 "변화가 없음"을 확인하는 한 번의 패스가 추가로 필요
4. 따라서 (최대 이동 거리 + 1)이 정답