백준 1377 버블 소트
문제링크
https://www.acmicpc.net/problem/1377
문제
키포인트
https://mygumi.tistory.com/84
해당 블로그의 글을 참조해 풀이했다.
내가 이해한대로 정리하면..
정렬했을때 자신의 원래 index보다 뒤에있는 원소들은 버블정렬이 진행되는동안 맨뒤에 큰 수들이 채워지면서 '매턴마다' '자기 자리를 찾을때까지' '앞으로만' '한칸씩' 간다.
(큰 수들이 뒤부터 채워지면서 앞으로 밀어냄!)
그렇기 때문에 앞으로 가장 먼 거리를 이동한 원소를 찾아내면 된다. 이를 위해 먼저 stl sort를 이용해 배열을 정렬시킨후 정렬전 index와 비교해 가장 오랫동한 이동한 원소가 이동한 거리+1을 출력하면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<pair<int, int>> v;
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
int num; cin >> num;
v.push_back({ num,i });
}
sort(v.begin(), v.end());
int maxn = 0;
for (int i = 0; i < v.size(); i++) {
maxn = max(maxn, v[i].second - i);
}
cout << maxn + 1;
}
후기
구현은 쉬운데 알고리즘을 생각하기가 어렵다
아직 많이 부족한듯 하다. 다음에 다시 풀어보자
Author And Source
이 문제에 관하여(백준 1377 버블 소트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bgg01578/백준-1377-버블-소트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)