[BOJ][Java] 1377번 버블 소트

문제 설명

문제 링크 : https://www.acmicpc.net/problem/1377

 

문제를 접근하면 C++ 을 이용하여 정렬을 하는데 이때 버블 소트 알고리즘을 이용해서 정렬 하였다.

위 문제에서는 오름차순 정렬을 하고있다.

버블 소트 알고리즘은 배열에서 arr[i] 값과 arr[i+1] 값을 비교하여 만약 arr[i] 값이 더 크다면

arr[i]와 arr[i+1] 의 값을 swap 한다. 이런식으로 하나하나 값을 비교하며 정렬하기 때문에

정렬에 필요한 시간복잡도는 O(N^2)이 된다.

 

해당 문제에서 C++ 로 작성된 코드를 보면

스왑이 한번도 일어나지 않는경우의 i의 값을 출력하는것을 알 수 있다.

 

단순히 위의 C++ 코드로 구현된 버블 소트 알고리즘을 자바로 옮겨서 풀 수 있지만

문제는 문제의 입력값이 최대 500,000 이기 때문에 버블소트 알고리즘으로 해결하면

시간초과가 발생한다.

 

따라서 다른 방식으로 접근해야 하는데 

우선 [10, 1, 5, 2, 3] 을 정렬하면 [1, 2, 3, 5, 10] 이 된다.

여기서 버블 소트의 특성을 생각해보면 정렬된 상태와 기존의 상태에서 

가장 왼쪽으로 많이 이동한 숫자가 곧 최소 버블소트의 실행 횟수라는 것을 알 수 있다.

이때 기존의 인덱스와 정렬된 상태의 인덱스 값을 비교하면 알 수 있기때문에

Map을 이용해서 해결했고 만약 동일한 숫자가 연속적으로 나올경우를 대비해서

Map<Integer, Queue<Integer>> 를 설정해서

기존의 인덱스들을 저장하고 정렬된 인덱스들을 기존의 인덱스값과 비교할 수 있도록 하였다.

 

package boj;

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

public class BOJ1377 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        Map<Integer, Queue<Integer>> map = new HashMap<>();

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

            arr[i] = num;
            if(map.containsKey(num)){
                map.get(num).add(i);
            }else{
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                map.put(num, q);
            }
        }

        Arrays.sort(arr);

        int max = 0;
        for(int i = 0; i < arr.length; i++){
            int gap = map.get(arr[i]).poll() - i;
            if(max < gap) max = gap;
        }

        System.out.println(max+1);

    }
}