버블 정렬의 swap이 한 번도 일어나지 않은 루프가 몇 번째인지 알아내는 문제이다. 안쪽 for문에서 한번도 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬되었다는 의미와 같으므로 프로세스를 종료하여 시간복잡도를 줄일 수 있다.
하지만 이 문제는 N의 최대 크기가 500,000이므로 시간복잡도가 인 버블정렬을 사용할 수 없다.
먼저 예제 입력을 위의 C++ 코드에 대입해서 생각해보자. 필자는 안쪽 for문의 swap이 발생하여 정렬된 데이터를 "|" 표시로 구분하도록 하겠다.
e.g. [10, 1, 5, 2, 3]
i = 1일때 1, 5, 2, 3, | 10
i = 2일때 1, 2, 3, | 5, 10
i = 3일때 1, 2, 3, | 5, 10
=> 3을 출력한 후 break를 통해 프로세스 종료
우리는 sort() 함수를 통해 먼저 배열을 정렬할 것이다. (시간복잡도 이므로 사용 가능)
그리고 정렬 전 배열의 인덱스는 변경하지 않은 채로 값을 오름차순을 나열하고, 정렬 후(sort 사용 후) 배열의 인덱스를 생각해보자.
-
정렬 전 배열의 index
value 1 2 3 5 10 index 1 3 4 2 0 -
정렬 후 배열의 index
value 1 2 3 5 10 index 0 1 2 3 4
여기서 정렬 전 index - 정렬 후 index를 하게되면 아래와 같다.
| value | 1 | 2 | 3 | 5 | 10 |
|---|---|---|---|---|---|
| index 차이 | 1 | 2 | 2 | -1 | -4 |
잘 생각해보면 각 요소의 인덱스 차이가 최초 위치를 기준으로 몇 칸 이동하였는지 알려주는 횟수와 동일하다.
e.g. 10은 오른쪽으로 4칸 => -4
e.g. 1은 왼쪽으로 1칸 => +1
안쪽 for문은 왼쪽에서 오른쪽으로, 다시 말해 i=0부터 N-i까지 순차적으로 탐색하므로 왼쪽으로 가장 많이 이동한 값(index 차이의 최댓값)에 1을 더하면 문제를 해결할 수 있다.
왜냐하면 왼쪽으로 가장 많이 이동한 값(=index 차이의 최댓값)이 안쪽 for문의 가장 마지막 실행 순서가 되고, swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 1을 더해야한다.
Python
따라서 파이썬의 소스코드는 아래와 같다.
import sys
input = sys.stdin.readline
N = int(input())
A = []
# 정렬 전 인덱스를 알아야 하므로 (값, 인덱스) tuple 형태로 저장
for i in range(N):
A.append((int(input()), i))
# 배열 오름차순 정렬
A.sort()
max = 0
# 전체 배열의 길이만큼 반복하면서
for i in range(N):
# 정렬 전 index - 정렬 후 index의 결과값 중
# 최댓값을 max에 저장
if max < A[i][1] - i:
max = A[i][1] - i
# 정답 출력
print(max + 1)참고로 sort() 함수는 리스트 안에 튜플이나 리스트가 있는 경우 (중첩리스트, 중첩된 iterable 객체 등) 첫 번째 요소를 기준으로 정렬하고 만약 첫 번째 요소가 같다면 두 번째 요소를 기준으로 정렬한다. 이를 사전순 정렬(lexicographical order)이라고 한다.
e.g. A = [(40, 0), (10, 1), (30, 2), (20, 3), (50, 4)]
A.sort() 호출
=> A = [(10, 1), (20, 3), (30, 2), (40, 0), (50, 4)]
e.g. B = [(10, 1), (10, 0), (20, 3)]
B.sort() 호출
=> B = [(10, 0), (10, 1), (20, 3)]
Java
따라서 자바의 소스코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class P_1377 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<Node> A = new ArrayList<>();
for (int i = 0; i < N; i++) {
int now = Integer.parseInt(br.readLine());
A.add(new Node(now, i));
}
Collections.sort(A);
int Max = 0;
for (int i = 0; i < N; i++) {
if (Max < A.get(i).index - i)
Max = A.get(i).index - i;
}
System.out.println(Max + 1);
}
}
class Node implements Comparable<Node>{
int value;
int index;
public Node(int value, int index) {
this.value = value;
this.index = index;
}
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}자바의 경우 Collections.sort(List<T> list) 메서드를 통해 정렬이 가능하다.
근데 자바는 파이썬과 달리 tuple 타입처럼 바로 넣을 수 있는 자료구조가 없으므로... 우리는 임의로 Node 클래스를 정의하였다.
따라서 Comparable<T> 인터페이스의 compareTo() 메서드를 오버라이딩하여 value를 기준으로 오름차순 정렬할 수 있도록 구현해야 한다.
