[백준:Java] 버블정렬(1838번)

백준 문제 : https://www.acmicpc.net/problem/1838

 

접근 방법

1. 제한 조건 확인하기 : 첫째 줄에는 정수 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 순서대로 주어진다. 주어지는 정수는 절댓값이 2,147,483,647을 넘지 않는다.

 

 

1초에 대략 1억개의 연산을 한다는 가정하에 O(n²)은 불가능하다는 것을 알 수 있습니다.

 

2. 규칙 찾기 : 버블 정렬을 했을 때 정렬 전 배열과 정렬 후 배열을 확인을 했을 때 종료되는 규칙을 찾을 수 있습니다.

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];
        int[] sortedArr = new int[N];
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(st.nextToken());

            arr[i] = n;
            sortedArr[i] = n;
        }

        Arrays.sort(sortedArr);

        // [30, 10, 44, 27, 49]
        System.out.println(Arrays.toString(arr));
        // [10, 27, 30, 44, 49]
        System.out.println(Arrays.toString(sortedArr));
    }
}

 

해당 예제의 결과는 2이며 3번째에 있는 27이 1번으로 이동했을 때 2번 반복하기 때문에 2입니다.

여기서 주의깊게 봐야 할 점은 0번째에 있는 30입니다. 언뜻 보았을 때 2번 반복한다라고 생각을 하지만 버블 정렬의 특징을 알아야합니다.

 

큰 숫자일 수록 해당 회차에 한 번에 많이 움직인다는 특징이 있으며 해당 30은 i 가 0일 때 바로 자기의 위치로 이동합니다.

 

정리

• 현재 비교하는 요소가 정렬 후 인덱스보다 크면 정렬 후 idx - 정렬 전 idx
• 정렬 후 인덱스보다 작다면 해당 배열에서 몇 번째로 큰 요소인 지

 

 

---

정답은 더보기 클릭

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());

        Map<Integer, Queue<Integer>> map = new HashMap<>();
        int[] sortedArr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(st.nextToken());
            sortedArr[i] = n;

            if (map.containsKey(n)) {
                map.get(n).offer(i);
            } else {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                map.put(n, queue);
            }
        }

        Arrays.sort(sortedArr);


        int maxDiff = 0;
        for (int i = 0; i < N; i++) {
            int num = sortedArr[i];

            int idx = map.get(num).poll();
            maxDiff = Math.max(maxDiff, Math.min(Math.abs(idx - i), N-i));
        }

        System.out.println(maxDiff);
    }
}