링크
https://www.acmicpc.net/problem/1377
문제 설명
정답률 34.980%
버블 소트 알고리즘을 다음과 같이 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이다.
5
10
1
5
2
3
출력 예제
3
풀이
문제의 코드를 보면 swap이 한 번도 일어나지 않은 때를 출력해야 한다. 이는 버블 정렬의 이중 for문에서 안쪽 for문이 swap이 일어나지 않았다는 것으로 이미 모든 데이터가 정렬됐다는 것을 의미한다.
N의 최댓값이 이므로 이중 for문으로는 시간 초과가 발생한다. 안쪽 for문이 몇 번 수행됐는지 구하기 위하여 안쪽 for문에서 swap이 일어날 때 데이터가 왼쪽으로 이동하는 경우는 최대 1번이다.
버블 정렬이 한 번 수행됐을 때를 생각해보면 정렬될 때 한 칸씩 이동한 것을 볼 수 있다.
- 정렬 전: 10 1 5 2 3
- 정렬 후: 1 5 2 3 10
이것으로 정렬 전후의 인덱스를 비교하면 안쪽 for문의 반복 횟수를 알 수 있다. 이때 정렬은 sort 메서드를 이용하는데 시간 복잡도는 O(nlogn)이 된다.
예제에서 정렬 전과 정렬 후를 비교하면 다음과 같다.
인덱스의 차이가 큰 것은 3-1와 4-2일 때이다. 이때 swap이 일어나지 않아도 반복문은 한 번 수행되므로 결과값에 +1을 해준다.
코드
//백준
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //5*10^5
List<Data> list = new ArrayList<>(); //Data 객체를 저장할 리스트
int[] index = new int[N]; //인덱스를 저장할 배열
for (int i = 0; i < N; i++) {
list.add(new Data(i, Integer.parseInt(br.readLine())));
index[i] = i;
}
//Data 객체를 value를 기준으로 정렬, O(nlogn) 시간 복잡도
list.sort((o1, o2) -> o1.value - o2.value);
//인덱스 배열의 값을 갱신
for (int i = 0; i < N; i++) {
Data data = list.get(i);
index[i] = data.index - index[i];
}
//인덱스 배열의 최댓값
int answer = Arrays.stream(index)
.max()
.orElseThrow();
System.out.println(answer + 1);
}
//인덱스와 값을 가지는 Data 클래스
static class Data {
int index;
int value;
public Data(int index, int value) {
this.index = index;
this.value = value;
}
}
}
백엔드