문제
bool change = false;
for (int =1; i<= n + 1; i++){
change = false;
for(int j = 1; j <= n - i; j++){
if ( a[j] > a[j+1] ){
change = true;
swap(a[j], a[j+1]);
}
}
if(change == false){
cout << i << '\n';
break;
}
}
위 버블 소트를 구현한 c++ 코드의 의도를 구하는 문제
1. 1번째 줄에 N이 주어진다
( 1 <= N <= 500,000)
2. 2번째 줄부터 N개의 줄에 A[1] ~ A[N] 까지 1개씩 주어진다
( 0 <= A[i] <= 1,000,000 )
3. 시간제한 2초
문제 분석
최대 500,000개까지 배열의 개수가 정해질 수 있으므로 O(N^2)일 경우 시간초과가 나게 된다
(버블 정렬은 시간복잡도가 O(N^2)이므로, 최대 개수는 10,000 이다 - 1초에 1억번 연산)
[해결방법]
1. 문제에서는 버블정렬이 이루어지는, 바깥쪽 for문의 횟수이다
2. 버블정렬의 경우, 최대값부터 정해지게된다 ( 최대 횟수는 맨 뒤의 숫자가 가장 작을때의 수이므로 N 이다 )
3. 버블정렬은 오른쪽으로는 안쪽 for문의 따라 움직이게 되고, 왼쪽으로 이동하는 숫자는 인쪽 for문 하나당 +1 위치이다
4. 왼쪽으로 가장 많이 움직인 인덱스 개수 + 1 이 for 문이 진행된 횟수이다.
문제 ) N : 5 / Array : 10, 1, 5, 2, 3
- 바깥쪽 for문 : 1
- 안쪽 for문
- 1,10,5,2,3
- 1,5,10,2,3
- 1,5,2,10,3
- 1,5,2,3,10 (10은 이제부터 고정)
- 이동횟수
| 1 |
+1칸 |
| 2 |
+1칸 |
| 3 |
+1칸 |
| 5 |
+1칸 |
| 10 |
-4칸 |
- 바깥쪽 for문 :2
- 안쪽 for문
- 1,5,2,3,10
- 1,2,5,3,10
- 1,2,3,5,10 (5,10 고정)
| 1 |
0칸 |
| 2 |
+1칸 |
| 3 |
+1칸 |
| 5 |
-1칸 |
| 10 |
0칸 |
- 바깥쪽 for문 :3
- 안쪽 for문
- 1,2,3,5,10 (변동 없음 - 버블정렬 종료)
| 1 |
0칸 |
| 2 |
0칸 |
| 3 |
0칸 |
| 5 |
0칸 |
| 10 |
0칸 |
즉, 각각 인덱스가 옮겨진 개수 중에 최대로 옮겨진 개수 + 1 이 바깥쪽 for문의 횟수가 된다
[이동 횟수]
1 : +1칸
2 : +2칸
3: +2칸
5: 0칸
10 : -4칸
최대가 +2 이므로, for문의 경우 정렬이 끝났더라도 한번 더 순회하므로, 정답 " 3 " 이다.
슈도코드
- 자바의 sort()기능을 이용하여 (시간복잡도 O(NlogN)), 정렬 후 인덱스와 정렬 전 인덱스의 차이를 이용하여 최대로 많이 왼쪽으로 이동한 횟수의 +1을 구하여 답을 구한다
단) 숫자가 왼쪽으로 움직였다가, 오른쪽으로 다시 위치되는 (ex] 5)의 경우 +-되므로 for문 횟수구하는 것에 영향을 끼치지 않는다
(즉 왼쪽(바깥쪽 for문 한번당 왼쪽으로는 한칸밖에 못움직임)으로 최대로 움직인 횟수가 바깥쪽 for문이 돈 횟수가 된다)
N(데이터 개수) A(데이터 배열)
for(N만큼 반복하기){
A배열 저장
}
A 배열 정렬하기
for(N만큼 반복하기){
A[i]의 정렬 전 index - 정렬 후 index 계산의 최대값 찾아 저장하기
}
최대값 +1 출력
index와 value 저장 클래스{
index,value가지며
value기준 오름차순 정렬함수 comparable 구현하기
}
구현하기
- Arrays.sort()의 객체 정렬의 경우 기준을 잡아줘야하므로, Comparable을 implements를 해야한다
- @Override compareTo()로, 기준을 설정해야함
- sort()함수에서 compareTo()를 호출하며 정렬을 진행
compareTo(mData o){
this.value - o.value;
}
(현재객체 기준)
this.value > o.value : 현재 객체가 뒤로감
this.value == o.value : 정렬 순서 유지
this.value < o.value : 현재객체가 앞으로감
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class App {
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(bf.readLine());
mData[] arr = new mData[size];
for(int i = 0; i<size; i++){
arr[i] = new mData(i, Integer.parseInt(bf.readLine()));
}
Arrays.sort(arr);
int MAX = 0;
for (int i =0; i< size; i++){
if (MAX < arr[i].index - i){ // arr[i].index 는 정렬전 index , i 는 현재 인덱스
MAX = arr[i].index -i;
}
}
System.out.println(MAX +1);
}
public static class mData implements Comparable<mData>{
private int index;
private int value;
public mData(int index, int value){
this.index = index;
this.value = value;
}
@Override
public int compareTo(mData o){
return this.value - o.value; // 오름차순 정렬
}
}
}