[알고리즘_코딩 테스트_JAVA] 버블 소트 프로그램 1 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 016 버블 소트 프로그램 1

문제 바로가기 💨 

 

⬜ 핵심 아이디어

버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제이다.

swap이 한 번도 일어나지 않았다. == 이미 모든 데이터가 정렬됐다.

로 볼 수 있다.

예를 들어,

10 1 5 2 3 에서 버블 정렬을 시작하면,

1 5 2 3 10 (10 fix)

1 2 3 5 10 (5,10 fix)

다음으론 swap횟수가 0이므로, 이미 모든 숫자(1,2,3)가 정렬 완료 되었음을 알 수 있다.

 

하지만 N의 범위가 50만이기때문에,버블정렬을 이용하면 N^2 시간초과가 발생한다. 따라서 안쪽 for 문이 몇 번 수행됐는지 구하는 다른 아이디어가 필요하다.

• 안쪽 for 문이 몇 번 수행됐는지 구하는 다른 아이디어
  • 특정 데이터가 안쪽 루프에서 swap으로 이동할 수 있는 최대거리는 1
  • 데이터 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값(최댓값) 을 찾는다.
  • 이는 내부 for 문에서 swap이 일어나서 반복한 반복문 (for) 횟수와 같다.

그리고 swap 이 일어나지 않는 반복문이 한번 더 실행되는 것을 감안해 최댓값에 1을 더한다.

결괏값이 양수면 앞으로(<<), 음수면 뒤로 이동(>>)을 뜻함

파이썬 풀이. 정렬 후 - 정렬 전

슈도코드 작성하기

java version

N(데이터 개수) A(데이터 배열, 단 클래스를 데이터로 담는 배열)
for(N만큼 반복)
{
    A 배열 저장
}
A 배열 정렬하기
for(N만큼 반복)
{
    A[i] 정렬 전 index - 정렬 후 index 계산의 최댓값을 찾아 저장하기
}
최댓값 + 1 을 정답으로 출력하기

별도 클래스 선언하기
mData(데이터 표현)
{
    index, value를 가지며
    value 기준 오름차순 정렬 함수 Comparable 구현하기
}

 

 

python version

N(데이터 개수)
A(데이터 저장 배열)

for(N만큼 반복)
{
    A 배열 저장
}

A 배열 정렬

for(N만큼 반복)
{
    A[i] 정렬 후 index - 정렬 전 index 계산의 최댓값을 찾아 저장하기
}

최댓값 + 1 을 정답으로 출력하기

 

JAVA

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

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	    int N = Integer.parseInt(reader.readLine());
	    mData[] A = new mData[N];
	    for(int i = 0; i < N; i++){
	        A[i] = new mData(Integer.parseInt(reader.readLine()),i);
	    }
	    Arrays.sort(A); // A 배열 정렬. O(nlogn) 시간 복잡도
	    int Max = 0;
	    for (int i = 0; i < N; i++){
	        if (Max < A[i].index - i){ // 정렬 전 index - 정렬 후 index 계산의 최댓값 저장하기
	            Max = A[i].index - i;
	        }
	    }
        System.out.println(Max + 1);
	}
}

class mData implements Comparable<mData> {
    int value;
    int index;
    
    public mData(int value,int index){
        super();
        this.value = value;
        this.index = index;
    }
    
    @Override
    public int compareTo(mData o){ // value 기준 오름차순 정렬하기
        return this.value - o.value;
    }
}

 

PYTHON

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
    arr.append( (int(input()), i) )

sorted_arr = sorted(arr) 
answer = [] 

for i in range(n):
    answer.append(sorted_arr[i][1] - arr[i][1])

print(max(answer) + 1)

 

파이썬 풀이 설명 추가 참조글 출처
https://infinitt.tistory.com/229