문제는 다음과 같다.
https://www.acmicpc.net/problem/1377
풀이는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Node [] arr = new Node[N];
for(int i = 0 ; i < N ; i++) {
int v = Integer.parseInt(br.readLine());
arr[i] = new Node(i, v);
}
//버블정렬 하면서, swap이 멈출때, 즉 정렬이 멈췄을때의 arr[i] 뽑아내기
Arrays.sort(arr);
int maxMinus = -1;
for(int i = 0 ; i < N ; i++) {
Node n = arr[i];
if(n.i - i > maxMinus) {
maxMinus = n.i - i;
}
}
//index 차가 가장 큰 값을 maxMinus에 저장
bw.write(String.valueOf(maxMinus + 1));
bw.flush();
bw.close();
}
//value값으로 정렬해줄 클래스 생성
static class Node implements Comparable<Node> {
int i, v; //index, value
public Node(int i, int v) {
this.i = i;
this.v = v;
}
public int compareTo (Node n) { //값 오름차순
return this.v - n.v;
}
}
}
우선, 버블정렬 알고리즘은 다음과 같다.
for(int i = 0 ; i < N ; i++) {
boolean isChanged = false;
for(int j = 0 ; j+1 < N - i ; j++) {
if(arr[j] > arr[j+1]) { //버블정렬 알고리즘
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
isChanged = true;
}
}
if(!isChanged) {
break;
}
}당연히 코드로 보면 이해가 안간다.
예시를 들어 설명을 하겠다. 10 1 2 5 3 을 다음 코드에 집어넣을 예정이다.
10 1 2 5 3
for문 i = 0를 돌면
(10 1 2 5 3 -> 1 10 2 5 3 -> 1 2 10 5 3 -> 1 2 5 10 3 -> 1 2 5 3 10)
1 2 5 3 10 //가장 큰 수 10이 맨 끝으로 왔다.
for문 i = 1를 돌면(1 2 5 3 10 -> 1 2 5 3 10 -> 1 2 5 3 10 -> 1 2 3 5 10 -> 1 2 3 5 10)
1 2 3 5 10 //두번째로 큰 수 5가 제자리를 찾았다.
for문 i = 2를 돌면 이미 오름차순 정렬이 되어있으므로(1 2 3 5 10),
if(arr[j] > arr[j+1]) 가 실행되지 않아
isChanged = true;가 실행되지 않고,
그에 따라
if(!isChanged) {
break;
}가 실행되어 2중 for문이 멈추게 된다.
여기까지가 혹여나 버블정렬을 모르시는 분들을 위한 설명이다.
즉, 한번의 2중 for문으로 abcde 라는 배열의 ab, bc, cd, de 값을 비교해가며 바꿔주어, 최댓값이 배열의 오른쪽에 쌓이는 정렬이다.
더 자세한 버블소트 설명은?
https://www.youtube.com/watch?v=h2_Lc8a8Ffw&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=14&t=2s
이제 문제를 보면,
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;
}
}이 c++ 소스코드를 동작시켰을때 어떤 값이 출력되는지를 구하라고 했다.
이 소스코드는, 위의 버블정렬이 멈추었을때, 아무것도 변하지 않았을때 멈추고, 해당 index를 뽑아내는 코드이다.
즉 위의 자바를 예를 들면,
//두번째 for문에서, swap이 한번도 일어나지 않았을때,
//즉 정렬이 완료되었을때 index를 뽑아내라!
if(!isChanged) {
System.out.println(i);
break;
}
이 코드인것이다.
그럼 버블정렬을 사용해도 되나?
안된다.
버블정렬은 시간복잡도 n^2의 알고리즘.
최악의 경우 문제에서 주어진 조건 N = 50만일때
50만 * 50만은,
제한시간 2초, 2억번의 계산 수를 훨씬 뛰어 넘는다.
그래서, Arrays.sort()정렬 후 (시간복잡도 nlogn)
index의 차의 최댓값을 구했다.
잘 생각해보자.
위의 10 1 2 5 3 을 예시로 들겠다.
그러면, 10과 5가 정렬된 후 for문이 break되면서, i = 2에서 멈춘다.
그리고 3을 뽑아내면 된다.
위의 수에서, 1, 2, 3은 정렬되어있고 5, 10이 정렬되어있지 않다.
그래서 그러면 정렬되어있는 수 중 가장 큰 index를 가진 3은, 왼쪽으로 두칸 밀려나게 된다.
(10 1 2 5 3 -> 1 2 3 5 10), i = 4에서 i = 2로.
즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값 + 1을 찾으면
버블정렬에서 swap이 멈추는 index가 된다.
그래서 풀이는 이전의 index를 기록할 수 있도록 노드라는 클래스를 만들었고,
값에 따른 정렬 후
가장 크게 차이나는 index를 maxMinus로 기록한 후 + 1 을 해주었다.
LIG Bring me here