[백준 1377] 버블 소트 (C#, C++) - soo:bak

문제 링크

1377번 - 버블 소트

설명

N개의 정수가 주어지는 상황에서, N (1 ≤ N ≤ 500,000)과 배열이 주어질 때, 특정 버블 소트 알고리즘이 몇 번의 외부 루프를 수행한 후 종료되는지 구하는 문제입니다.

주어진 버블 소트는 한 번의 패스에서 교환이 일어나지 않으면 정렬이 완료된 것으로 보고 종료합니다.

접근법

주어진 버블 소트 알고리즘을 직접 시뮬레이션하면 O(N²) 시간이 걸려 N = 500,000일 때 시간 초과가 발생합니다.

대신 버블 소트의 특성을 분석하여 효율적으로 계산할 수 있습니다.

버블 소트는 인접한 두 원소를 비교하여 왼쪽이 더 크면 교환하는 방식입니다.

한 번 순회할 때 각 원소는 최대 한 칸씩만 왼쪽으로 이동할 수 있지만, 오른쪽으로는 여러 칸 이동할 수 있습니다.

따라서 어떤 원소가 최종 위치까지 왼쪽으로 k칸 이동해야 한다면 최소 k번 반복해야 합니다.

모든 원소 중 왼쪽으로 이동해야 하는 최대 거리가 필요한 최소 반복 횟수이며, 문제에서 요구하는 답은 이 값에 1을 더한 것입니다.

각 원소를 (값, 원래 인덱스) 쌍으로 저장한 후 값을 기준으로 정렬합니다.

정렬 후 위치 i에 있는 원소의 원래 인덱스가 idx라면, 왼쪽으로 이동한 거리는 idx - i입니다.

모든 원소에 대해 이 거리의 최댓값을 구한 후 1을 더하면 답이 됩니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  struct Info : IComparable<Info> {
    public int val;
    public int idx;

    public int CompareTo(Info other) {
      var c = val.CompareTo(other.val);
      if (c != 0) return c;
      return idx.CompareTo(other.idx);
    }
  }

  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var list = new List<Info>(n);

      for (var i = 0; i < n; i++) {
        var x = int.Parse(Console.ReadLine()!);
        list.Add(new Info { val = x, idx = i });
      }

      list.Sort();

      var maxMove = 0;
      for (var i = 0; i < n; i++) {
        var move = list[i].idx - i;
        if (move > maxMove)
          maxMove = move;
      }

      Console.WriteLine(maxMove + 1);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

struct Info {
  int val, idx;

  bool operator < (const Info& other) const {
    if (val == other.val) return idx < other.idx;
    return val < other.val;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vector<Info> v;
  v.reserve(n);

  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    v.push_back({x, i});
  }

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

  int maxMove = 0;
  for (int i = 0; i < n; i++) {
    int move = v[i].idx - i;
    if (move > maxMove)
      maxMove = move;
  }

  cout << maxMove + 1 << "\n";

  return 0;
}