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

문제

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

1377번: 버블 소트

 

 

풀이

1. sort() 함수로 배열 정렬 ⇒ 시간 복잡도 O(nlogn)

 

2. 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾는다.

  ⇒ 정렬 전 index - 정렬 후 index의 최댓값 + 1

  * 1 : swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안

 

정렬(Sort) 알고리즘

정렬(Sort) 알고리즘

 

 

코드

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

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

  int N;	// 데이터 개수
  cin >> N;

  vector<pair<int, int>> A(N);	// 데이터 저장 배열
  // 배열 A 저장
  for(int i = 0; i < N; i++)
  {
    cin >> A[i].first;
    A[i].second = i;
  }

  sort(A.begin(), A.end());	// 배열 A 정렬 시간 복잡도 : O(nlogn)

  int max = 0;
  for(int i = 0; i < N; i++)
  {
    // 정렬 전 index - 정렬 후 index를 계산한 값 중 최댓값을 찾아 저장
    if(A[i].second - i > max)
    {
      max = A[i].second - i;
    }
  }

  cout << max + 1;	// 최댓값 + 1을 정답으로 출력

  return 0;
}

 

 

오답

안 쪽 for 문은 1 ~ (n - j)까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap 수행

  ⇒ 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾는다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

  int N;
  cin >> N;
  vector<pair<int, int>> A(N);

  for(int i = 0; i < N; i++)
  {
    cin >> A[i].first;
    A[i].second = i;
  }

  sort(A.begin(), A.end());  // 배열 A 정렬 시간 복잡도 : O(nlogn)
  int Max = 0;

  for(int i = 0; i < N; i++)
  {
    // 정렬 전 index - 정렬 후 index를 계산한 값 중 최댓값을 찾아 저장
    if(Max < A[i].second - i)
    {
      Max = A[i].second - i;
    }
  }

  cout << Max + 1 << endl;
}