BOJ_1377_버블소트(Java)

[Gold II] 버블 소트 - 1377

문제 링크

성능 요약

메모리: 47920 KB, 시간: 300 ms

분류

정렬

제출 일자

2024년 8월 26일 04:16:51

문제 설명

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

정답을 출력한다.

코드

• 풀이 1 : 메모리 47920KB, 시간 300ms

import java.io.*;

public class Main {
	static int N, arr[], count[], sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        count = new int[1000001];

        /**
         * 각 숫자 등장횟수 세기
         * 인덱스값의 숫자가 몇번 등장했는지 저장
         */
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            count[arr[i]]++;
        }

        /**
         * 누적 합 계산
         * count 순회하며 각 숫자보다 작거나 같은 숫자들의 총 개수 계산
         * 이후 count[i]는 i보다 작거나 같은 숫자의 개수 - 1을 나타냄
         */
        sum = 0;
        for (int i = 0; i <= 1000000; i++) {
        	sum += count[i];
            count[i] = sum - 1;
        }

        /**
         * 최대 이동 거리 계산
         * 각 숫자의 현재 위치와 정렬 후 위치의 차이 중 최댓값 찾기
         * i - count[arr[i]]: 현재 위치 - 정렬 후 위치
         */
        int ans = 0;
        for (int i = 0; i < N; i++) {
        	ans = Math.max(ans, i - count[arr[i]]);
        }

        System.out.println(ans + 1);
    }
}

• 풀이 2 : 메모리 82748KB, 시간 1488ms

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

public class Main {
	
	public static class Data implements Comparable<Data>{
		int value;
		int idx;
		
		public Data(int value, int idx) {
			this.value = value;
			this.idx = idx;
		}

		@Override
		public int compareTo(Data o) {
			return this.value - o.value;
		}
	}
	
	static BufferedReader br;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Data[] data = new Data[N];
		
		for(int i=0; i<N; i++) {
			data[i]	 = new Data(Integer.parseInt(br.readLine()), i);
		}
		Arrays.sort(data);
		
		int max = 0;
		for(int i=0; i<N; i++) {
			if(max < data[i].idx-i) max = data[i].idx -i;
		}
		System.out.println(max+1);
	}
}