728x90
문제 설명
문제
버블 소트 알고리즘을 다음과 같이 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
5
10
1
5
2
3
예제 출력 1
3
예제 입력 2
5
1
3
5
7
9
예제 출력 2
1
풀이
import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
A.append((int(input()), i))
Max = 0
sA = sorted(A)
for i in range(N):
if Max < sA[i][1] - i:
Max = sA[i][1] - i
print(Max + 1)
- 버블 정렬을 어느 인덱스에서 멈춰서 시간복잡도를 줄일 수 있는지를 구하는 문제이다.
- 문제에서 주어진 것과 마찬가지로 버블 정렬을 구현해서 답을 구하려고 하면 시간 초과가 뜨기 때문에 다른 아이디어로 풀어야한다.
- 버블 정렬의 경우 한 번 swap 할 수 있는 거리는 최대 1이다.
'원본 리스트 인덱스 - 정렬된 리스트 인덱스'를 하면 오른쪽에서 왼쪽으로 얼마만큼 이동했는지 알 수 있다. 가장 큰 이동 횟수만큼 swap이 동작했다는 것을 알 수 있다. break 조건은 change == false이므로 마지막으로 도는 반복문에서 swap이 한 번도 일어나지 않아야 하므로 가장 큰 이동 횟수 + 1을 한 것이 정답이다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 / 정렬] 23968 : 알고리즘 수업 - 버블 정렬 1 (python) (0) | 2024.03.24 |
---|---|
[백준 / 정렬] 23881 : 알고리즘 수업 - 선택 정렬 1 (python) (0) | 2024.03.24 |
[백준 / 큐] 10828 : 스택 (python) (0) | 2024.03.19 |
[백준 / 큐] 1966 : 프린터 큐 (python) (0) | 2024.03.19 |
[백준 / 투 포인터] 1306 : 달려라 홍준 (python) (2) | 2024.03.18 |