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 ```java 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` ```java 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);
} }

```