[BaeKJoon] 1377번: 버블 소트 (Python)

1일 1문제 11일차!

오늘 풀어볼 문제는 버블소트 입니다.

1377번: 버블 소트

 

이 문제는 아래의 코드의 결과가 어떤 것이 출력되는지 답을 구하는 문제입니다.

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

 

먼저 위의 C 코드를 잘 살펴보면 앞에서부터 하나씩 인덱스를 비교해가면서 

앞의 인덱스의 원소 값이 바로 뒤의 인덱스의 원소 값보다 클 경우

swap함수를 통해 두 개의 위치를 바꾸어주는 코드입니다.

그러면서 처음에 false로 초기화 되어있는 change 변수를 true로 바꾸어 줍니다.

그 후에 change 변수가 true가 아닐때, 즉 swap이 바뀌지 않으면

마지막으로 탐색한 index의 위치를 출력하고 반복문을 중단하는 코드입니다.

 

위의 코드를 그림으로 살펴보면 아래와 같습니다. 그림은 키노트로 작성하였습니다.

잘 살펴보면

 

정렬이 될때마다 숫자가 왼쪽으로 이동한다는 겁니다.
그럼 원래 인덱스와 정렬된 인덱스를 비교했을때 차이가 나게 됩니다. 
정렬한 상태의 인덱스에서 정렬하기 전의 인덱스를 빼주면 왼쪽으로 간 숫자의 인덱스는 양수를 가지게 됩니다.
여기서 그 양수의 값에 +1 을 해주면 버블정렬이 진행된 횟수입니다.

 

코드로 구현해보면

import sys

N = int(input())

nums = []
indexs = []

for i in range(N):
    num = int(sys.stdin.readline())
    nums.append(num)
    
sorted_nums = sorted(nums)

answer = 0

for i in range(N):
    indexs.append(nums.index(sorted_nums[i]))
    
    answer = max(answer, indexs[i]-i)
    
print(answer+ 1)

결과는!

시간초과가 났습니다.

sorted하고 index하고 하는 과정에서 시간이 오래걸리지 않았나 생각이들어 append의 형식을 바꾸어보았습니다.

import sys

N = int(input())

nums = []

for i in range(N):
    num = int(sys.stdin.readline())
    nums.append((num, i))
    
sorted_nums = sorted(nums)

answer = 0
for i in range(N):
    answer = max(sorted_nums[i][1] - i + 1, answer)
    
print(answer)

결과는!

 

SOMJANG/CODINGTEST_PRACTICE