[자바] 백준 23970 - 알고리즘 수업 - 버블 정렬 3 (java)

 문제 : boj23970

---

 

필요 알고리즘 개념

• 애드 혹
  • 정형화된 방식이 존재하지 않고 이 문제만의 아이디어를 생각해내야 한다. 
• 정렬
  
  • 기본적인 정렬 방식을 알아야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  당연히 직접 버블정렬을 진행하면서 비교할 시, 버블 정렬이 O(N^2)이고 비교가 O(N)이므로 O(N^3)이 걸리게되어 시간초과가 나게 된다. 내 경우엔 정형화된 방식이 아니고 아이디어를 내서 시간을 줄여 O(N^2)으로 진행했으므로 태그는 애드혹으로 판단했다.

 

  이하 설명의 편의를 위해, 버블정렬의 두 루프에 대해 루프A, 루프B라 호칭한다.

 

  내 의식의 흐름은 다음과 같았다.

1. 결국 중요한건 매번 O(N)이 걸리는 비교 횟수를 줄이는 것이다.

 

2. 모든 경우에 대해 버블정렬을 전부 해볼 필요는 없다. B에서 뒤에서부터 내림차순으로 정렬된 구간까지만 A에서 버블 정렬을 진행하면, 그 이후로는 한 번의 루프B만 더 돌면 된다.(A에서 B를 만들어가는 과정인 셈이므로, B에서 정렬이 끝난 부분까지 일단 진행하고 그 이후 한번만 더 루프B를 진행해보는 것이다. 그 이후로는 당연히 진행할 필요가 없다.)

-> 예를들어 예제 입력 1의 B를 보면, 뒤에서부터 정렬된 부분은 '5 6' 부분이다.

-> 따라서 A도 맨 뒷부분이 '5 6'이 될때까지만 버블정렬을 해주자. A에 대해 루프B를 한번 진행해주면

4 6 5 1 3 2 -> 4 5 1 3 2 6 

다시한번 루프B를 진행해주면

4 5 1 3 2 6 -> 4 1 3 2 5 6

 

3. '2'를 진행할 때 비교가 필요할까? A에서 처음 루프B를 돌면서 6을 맨 오른쪽으로 옮기는 동안은 어차피 B와 동일하지 않음이 보장되므로 필요가 없다. 다만 A가 처음에 '4 5 1 3 2 6' 처럼 6이 맨 오른쪽이었을 수 있으므로 그 때를 대비해서 어쨌든 타겟이 되는 숫자('2'의 처음 루프B에서의 '6'과 같이)가 원하는 위치에 도달했다면 비교가 필요하다.

 

4. '2'~'3'에 해당하는 로직은 코드에서 다음과 같다. 설명은 주석으로 달아두었다. '2'~'3'은 대략 O(N^2)이 소요된다.

Arrays.sort(tmp);	// B의 맨뒤부터 어디까지 진행할지 보기 위해 정렬
int len = n;
for (int i = n-1; i >= 0; i--) {
    if (b[i] != tmp[i]) break;	// B의 정렬된 맨 뒷부분구간에 대해 버블 정렬 진행
    for (int j = 0; j < len-1; j++) {
        if (a[j] > a[j+1]) {
            int swap = a[j];
            a[j] = a[j+1];
            a[j+1] = swap;
            if (a[len-1] == b[len-1] && isSame(a, b)) {	// 타겟 위치가 동일한 경우에만 비교(isSmae)를 진행
                System.out.println(1);
                return;
            }
        }
    }
    len--;
}

 

5. '2'~'3' 과정을 마쳤다면, 이제 루프B를 한번만 진행해주면서 원래 버블정렬처럼 교환하면서 비교해주면 된다! 이 과정은 O(N^2)이다. 따라서 전체 과정은 O(N^2)에 가능하다.

for (int i = 0; i < n-1; i++) {
    if (a[i] > a[i+1]) {
        int swap = a[i];
        a[i] = a[i+1];
        a[i+1] = swap;
        if (isSame(a, b)) {	// 이젠 그냥 매번 SWAP이 일어났다면 비교해준다.
            System.out.println(1);
            return;
        }
    }
}

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        int[] b = new int[n];
        int[] tmp = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = tmp[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) b[i] = Integer.parseInt(st.nextToken());

        if (isSame(a, b)) {
            System.out.println(1);
            return;
        }
        
        Arrays.sort(tmp);
        int len = n;
        for (int i = n-1; i >= 0; i--) {
            if (b[i] != tmp[i]) break;
            for (int j = 0; j < len-1; j++) {
                if (a[j] > a[j+1]) {
                    int swap = a[j];
                    a[j] = a[j+1];
                    a[j+1] = swap;
                    if (a[len-1] == b[len-1] && isSame(a, b)) {
                        System.out.println(1);
                        return;
                    }
                }
            }
            len--;
        }
        if (isSame(a, b)) {
            System.out.println(1);
            return;
        }
        for (int i = 0; i < n-1; i++) {
            if (a[i] > a[i+1]) {
                int swap = a[i];
                a[i] = a[i+1];
                a[i+1] = swap;
                if (isSame(a, b)) {
                    System.out.println(1);
                    return;
                }
            }
        }

        System.out.println(0);
    }

    private boolean isSame(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}