[백준/파이썬] 1377 버블 소트

[백준/파이썬] 1377 버블 소트

 

📌 문제 

버블 소트 알고리즘을 다음과 같이 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이다.

 

 

📣 출력

정답을 출력한다.

 

 

 

---

 

 

 

💎 문제분석하기

 

도대체 무엇을 어떻게 하라는지 이해가 안돼서 이해하는데 시간이 걸렸다. 

 

예제로 주어진 입력과 출력을 통해 유추하여 답을 찾으라는 의도 같다. 

 

버블소트 로직을 이해하고 무엇을 구하라는지 이해하면 쉽게 풀리는 문제이다. 

 

먼저 2번 예제를 손으로 풀어보면 다음과 같다. 

 

 

 

즉 sort가 일어나는 iteration의 횟수를 구한 값을 구하라는 요청이며, 이는 위와 같이 

 

정렬전 idx - 정렬 후 idx한 값 중 max를 찾아 마지막으로 +1을 해주는 방식으로 구해질 수 있다. 

 

버블 소트에서 이중 for문을 돌면서 두번째 for문에서 소트가 일어나지 않는 상황이 발생한다면 정렬이 다 되었다는 의미이며, 이때 break를 한 후 j를 리턴한다면 정답이 출력될 것이다. 하지만 이와 같은 방식은 50만^2의 시간 복잡도를 발생시키면서 시관 초과로 실패하게 된다. 

 

따라서 위에서 찾는 방식의 아이디어가 필요하며, 이 아이디어를 적용한다면 쉽게 풀리는 문제이므로 사실상 아이디어 싸움의 문제라고 할 수 있겠다. 

 

파이썬의 함수를 활용하는 방식으로 max값 까지 한번에 구하는 코드를 작성했는데 시간초과가 떴다. 

 

import sys

n = int(sys.stdin.readline())
arr = []

for i in range(n):
    arr.append( int(sys.stdin.readline()))

new_arr = sorted(arr)
max =0

for i in range(n):
    idx_of_new_array_at_original_array = arr.index(new_arr[i])
    if max < idx_of_new_array_at_original_array - i:
        max = idx_of_new_array_at_original_array - i
    
print(max+1)

 

그래서 인덱스를 같이 저장하고 계산하는 방식을 사용해야 했다. 

 

 

 

💡 코드 구현하기

 

import sys

n = int(sys.stdin.readline())
arr = []

for i in range(n):
    arr.append( (int(sys.stdin.readline()), i) )

new_arr = sorted(arr)
answer = []

for i in range(n):
    answer.append(new_arr[i][1] - arr[i][1] +1)
    
print(max(answer))

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편