1377.py

# 버블 소트
# 시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
# 2 초	128 MB	21709	6875	5510	35.386%

# 문제
# 버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

# bool changed = false;
# for (int i=1; i<=N+1; i++) {
#     changed = false;
#     for (int j=1; j<=N-i; j++) {
#         if (A[j] > A[j+1]) {
#             changed = true;
#             swap(A[j], A[j+1]);
#         }
#     }
#     if (changed == false) {      => 이 부분이 중요하다.
#         cout << i << '\n';       버블 정렬이 끝났을 때 알고리즘이 돈 횟수를 출력함
#         break;
#     }
# }
# 위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

# 위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

# 입력
# 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

# 출력
# 정답을 출력한다.


# 분석하기
# 1. 버블 정렬에서 swap 연산이 한 번도 일어나지 않는 루프가 언제일지 알아내는 문제이다.
# 핵심 이론을 떠올려보자
# 버블 정렬의 이중 for문에서 안쪽 for문 전체를 돌 때
# swap 연산이 일어나지 않는 다는 것은 이미 모든 요소가 정렬되었음을 의미한다.
# 이때 프로세스를 바로 종료해 시간 복잡도를 줄일 수 있다.

# 하지만 이 문제는 n <= 500,000이므로 버블 정렬의 시간 복잡도를 생각하면, 시간 초과가 발생할 수 있다.
# 따라서 안쪽 for문이 몇 번 수행됐는지 구하기 위해 다른 아이디어가 필요하다.

# other idea
# 안쪽 루프는 1 ~ n-j까지 swap 연산을 수행
# 이는 특정 요소가 안쪽 루프에서 swap 연산으로 인해 왼쪽으로 이동할 수 있는 최대 거리가 1임을 의미
# 따라서 요소를 정렬하기 전 index와 후의 index를 비교하여 왼쪽으로 가장 많이 이동한 값을 찾으면 된다!!
# 정렬전 index - 정렬후 index가 가장 큰 값을 찾자.


# 슈도코드
# n 데이터 갯수, A 데이터 리스트, 클래스로 데이터를 담음

# for n:
#     A에 데이터 저장

# A 리스트 정렬

# for n:
#     A[i] 정렬 전 index - 정렬 후 index의 값 중 최댓값을 찾아 저장
#     최댓값 + 1을 답으로 출력(swqp 연산이 한 번도 일어나지 않는 반복문이 한 번 더 실행될 것을 감안하여 +1)