Java 백준 문제풀이 (47) 버블 소트

일주일간 코딩한다고 알고리즘 손도 못대고 있다가, 방금 카카오 공채 코테 2문제 풀다 때려치우고 내 심각성을 느끼고 다시 백준 한 문제 풀었다..

 

일단 이 문제는 C++을 모르면 문제 자체를 이해할 수 없다. 난 그냥 눈치껏 풀어보고 의미는 나중에 찾아보긴 했다.

어려운 게 아니니 그냥 알아두자..

cout << i << '\n'은 자바로 따지자면 printf("\d\n", i)랑 비슷하다.

 

결국, changed==false일 때 i의 수를 출력한다는 것이고, 우리는 그 수를 구해야 한다.

 

거품 정렬 알고리즘이 뭔지 모른다면 아래 글을 읽어보자.

changed가 왜 있는지도 알 수 있다.

 

https://7357.tistory.com/137?category=1065986 

거품 정렬(Bubble Sort)에 대해 알아보자 (feat. JAVA)

 

이제 거품정렬과 changed의 존재 의미를 안다고 가정한다고 진행하겠다.

changed가 false라는 것은 더 이상 순서를 바꿀 값이 없다는 것을 의미하고, 우리는 주어진 배열에서 어느 시점에 정렬이 완료되는지 구하면 된다.

 

" 헉 ㅋㅋ 그러면 문제에 있는 예제 그대로 넣어서 답 구하면 되겠네요 ㅋㅋ 날로 먹을 수 있네 "

 

N의 최대 값이 500,000인데 거품 정렬의 시간 복잡도는 O(n^2)이다.

단순 연산이니 초당 1억이 아니라 10억회의 연산을 수행할 수 있다고 가정해도 때 계산기를 두들겨보면 문제에서 제시하는 2초는 턱없이 부족하다는 사실을 알 수 있다.

 

O(nlogn)의 시간 복잡도는 어떨까? 이제야 ssap가능해 보인다.

그러면 O(nlogn)의 시간 복잡도를 가진 방법으로 해결해보자. 어떤 방법이 있을까?

 

우선 거품정렬의 changed가 언제 false인지 다시 한 번 생각해보자. 더 이상 순서를 바꿀 값이 없다는 것이다.

그러면 순서가 바뀌기 전까지 for(int j=1; j=N-1-i; j++) 안에서는 어떤 일이 일어나고 있는가?

인접한 인덱스를 비교하여 큰 수가 좌측에 있다면 우측으로 한 칸씩 움직인다.

 

역으로 생각했을 때, 큰 수는 자신보다 큰 수를 만날 떄까지 우측으로 한 칸 씩 움직이지만 우측에 위치하고 있는 작은 수는 어떻게 움직일까?

1회 반복 시 작은 수는 스스로가 어떤 수이건 간에 "무조건" 단 한 칸만 좌측으로 움직인다. 

 

즉, changed가 false라는 것은 더 이상 좌측으로 이동할 작은 수가 없다는 뜻이고, 그 이전까지는 계속해서 좌측으로 이동하던 작은 수가 있다는 뜻이다.

이게 이해가 안되면 거품 정렬 복습하자.

 

그러면 우리에게는 두 가지 단서가 주어졌다.

1. O(n^2) 멈춰! 최소 O(nlogn)의 방법으로 풀어야 한다.

2. 더 이상 작은 수가 좌측으로 이동하지 않는 경우를 찾아야 한다.

 

그러면 기존 배열에서 O(nlogn)의 시간 복잡도를 가진 알고리즘으로 정렬한 뒤 바뀐 인덱스를 체크하면 되겠네요.

여기까지는 생각했으나 난 도저히 기존 배열과 바뀐 배열의 인덱스 차이를 구할 방법이 O(n^2)의 시간 복잡도 알고리즘 밖에 생각나지 않았다..

 

따라서 결국 찾아보고 풀어본 뒤 오늘 다시 복습 중임 ㅎㅎ..

여러분도 적당히 고민해보고 답을 보십쇼.. 화이팅

아마 자바를 능수능란하게 다룰 수 있는 분이 아니면 완전히 스스로 풀기는 힘들 듯하니 너무 시간 낭비하지 않는 게 정신 건강에 이로울 수도 있다.

 

정답은 아래에

(힌트 : Comparable을 구현한 클래스를 이용해볼까요. )

(힌트2 : 실제 i가 출력되는 시점은 마지막으로 인덱스가 이동하고 한 번 더 반복될 때라는 사실을 명심하십시오. )

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        Temp[] arr = new Temp[N];
        for (int i=0; i<N; i++) {
            arr[i] = new Temp(i, Integer.parseInt(br.readLine()));
        }
 
        Arrays.sort(arr);
        int max = 0;
 
        for (int i=0; i<N; i++) {
            if ( i != arr[i].getIndex() ) {
                max = Math.max( arr[i].getIndex() - i, max );
            }
        }
 
        System.out.println(max + 1);
    }
}
 
class Temp implements Comparable<Temp> {
    private final int index;
    private final int value;
 
    public Temp(int index, int value) {
        this.index = index;
        this.value = value;
    }
 
    @Override
    public int compareTo(Temp o) {
        return this.value - o.value;
    }
 
    public int getIndex() {
        return this.index;
    }
 
    public int getValue() {
        return this.value;
    }
}