문제 풀이 날짜: 2025-08-17
💡Github URL
💡 초기 접근
버블 소트에서 pass가 몇 번 일어나는지를 물어보는 문제.
cf) 버블 소트는 1 pass 내에서 swap이 한 번도 일어나지 않으면, 정렬이 완료된 상태라고 판단하여 종료됨.
💡알고리즘 설계
입력값이 크기 때문에 버블 소트 O(N^2)를 그대로 사용하면 시간 초과 발생.
때문에 O(N) or O(NlogN) 이하의 시간 복잡도로 구현해야 함.
버블 소트에서는 1 pass가 일어날 때 데이터가 왼쪽/오른쪽으로 최대 1칸 이동할 수 있음. 때문에 정렬 전/정렬 후 데이터 위치(index)의 최대값 + 1 만큼의 pass가 일어나야만 정렬이 완료된다는 것을 의미. (여기서 +1은 정렬이 완료되었는지 확인하는 마지막 pass, 이 pass에서는 swap 발생 X) 때문에 정렬 전/정렬 후 데이터의 index 차이 중 최댓값을 찾아야 함.
Arrays.sort()를 사용하면 TimSort 기반이라 시간 복잡도가 O(NlogN)이기 때문에 구현이 가능함.
💡코드
메모리: 86044 KB, 시간: 1520 ms
import java.io.*;
import java.util.*;
class Main {
static BufferedReader br;
static class Node implements Comparable<Node>{
int index;
int value;
Node(int index, int value){
this.index = index;
this.value = value;
}
public int compareTo(Node o) {
return this.value - o.value; // 오름차순
}
}
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Node[] list = new Node[N];
for(int i=0; i<N; i++){
list[i] = new Node(i, Integer.parseInt(br.readLine()));
}
Arrays.sort(list);
int maximum = Integer.MIN_VALUE;
for(int i=0; i<N; i++){
int tmp = list[i].index - i;
if(maximum < tmp){
maximum = tmp;
}
}
System.out.println(maximum + 1);
}
}💡시간복잡도
O(NlogN)
💡틀린 이유
1. 시간 초과
import java.io.*;
import java.util.*;
class Main {
static BufferedReader br;
static StringBuilder sb;
static BufferedWriter bw;
static void swap(int[] array, int a, int b){
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] numbers = new int[N];
for(int i=0;i<N;i++){
numbers[i] = Integer.parseInt(br.readLine());
}
int end = N-1;
boolean swapCheck = true;
int cnt = 1;
while(end >= 0){
swapCheck = true;
for(int i=0; i<end; i++){
if(numbers[i] > numbers[i+1]) {
swapCheck = false;
swap(numbers, i, i+1);
}
//System.out.println(Arrays.toString(numbers));
}
if(swapCheck) {
System.out.println(cnt);
break;
}
else end --;
cnt ++;
}
}
}단순하게 버블 소트를 구현하고, 버블 소트가 종료되는 시점까지 몇 번 pass 되었는지 카운팅하려고 했음. 그러나 O(N^2)인데 N<= 500,000 이라 시간 초과 발생.
2. 정렬해야 하는 수의 갯수
import java.io.*;
import java.util.*;
class Main {
static BufferedReader br;
static StringBuilder sb;
static BufferedWriter bw;
static void swap(int[] array, int a, int b){
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] numbers = new int[N];
for(int i=0;i<N;i++){
numbers[i] = Integer.parseInt(br.readLine());
}
int cnt = 1;
int minimum = numbers[N-1];
for(int i=N-2; i>=0; i--){
if(numbers[i] < minimum) minimum = numbers[i];
else if(numbers[i] > minimum) cnt ++;
else continue;
}
System.out.println(cnt);
}
}시간 복잡도 O(N)을 기대하면서, 뒤에서부터 순회하면서 정렬해야 하는 갯수를 카운팅하려고 했음. 뒤에서부터 순회하면서 자신보다 큰 수가 있으면 cnt + 1, 더 작은 수가 나오면 최솟값을 갱신하면서 끝까지 순회하고, cnt + 1을 결과로 내려고 했음.
그러나 이 시도는 버블 소트 자체를 잘못 이해한 접근이었음.
버블 소트는 단순하게 1 pass에 1개의 값만 뒤로 이동하여 정렬 시 본인의 위치로 이동하는 것이 아니라, 1 pass에 다른 모든 값들도 앞으로 1칸 씩 이동하는 결과가 나타남. 때문에 이 방식대로 하면 1 pass 내에 정렬될 수 있는 여러 개의 수를 전부 개별로 카운팅하기 때문에 오류 발생.
3. 구현 실패
성공한 풀이를 구현하려고 했으나, 처음에는 Map 자료구조를 사용하려고 했음.
Map<Integer, int[]> 형태로 Map을 생성하여
value: { 원본 배열에서의 index, 정렬 이후 배열에서의 index}형태로 저장하려고 하였으나, 이 방식은 value가 같은 경우, 즉 배열 내 같은 숫자가 여러 개 존재하는 경우 문제가 발생했음. {1, 2, 2, 2, ...} 이런 경우에 value가 중복되어 문제 발생.
