버블 정렬 프로그램(백준 - 1377번)

백준 1377번은 문제 이해부터 어려웠다(개인적인 의견).

직접적으로 어떤 코드를 작성해야하는지 감을 잡기 어려웠다.

이러한 문제들을 접하다 보니 코테의 높은 장벽에 그만둔 전적이 2번정도 있다.

결국은 책과 구글링의 힘을 빌려 문제 이해까지는 도움을 받기로 합의를 봤다.

---

 

문제 이해

버블 정렬이 된 C++ 코드가 있다.

이때 버블 정렬된 코드가 출력하는 값과 같은 값을 출력하는 코드를 작성해야 한다. 

그러기 위해서는 C++ 코드가 출력하는  값이 무엇인지 파악해야 했다.

 

입력

입력은 수의 개수인 N과 버블 정렬시킬 N개의 각 수들을 한 줄씩 입력한다.

 

출력

출력 값의 의미가 무엇인지가 중요했다. 출력 값은 완전히 버블 정렬 시 몇 번째에서 완전히 버블 정렬되는 지이다.

 

해결책

C++코드대로 코드를 돌려도 원하는 값이 출력되기는 하지만 N이 500,000까지의 수이다. 즉 최대로 버블 정렬이 돌아갔을 때 2초를 초과할 수 있다. 그렇다면 중첩 for문이 있어서는 안된다. 중첩 for문을 돌리지 않고 버블 정렬 완료 시 정렬이 돌아간 횟수를 알아야 한다. 중첩 for문에서 외부 for문은 버블 정렬의 횟수이고 내부 for문은 버블 정렬을 돌고 있는 과정이다. 외부 for문을 알아내야한다. 이는 내부 for문이 몇 번 돌았는지의 수와 같다.

우선 내부 for문이 돌아간 횟수를 알기 위해서 중첩 for문이 사용되지 않고 알아낼 수 있어야 한다. 내부 for문이 1번 돌아갔을 때 나타나는 특징은 각 수들이 최대 왼쪽으로 1번 이동한다. 이때 모든 수들이 왼쪽으로 이동하지 않으면 버블 정렬이 모두 완료된 상태로 이때의 횟수가 출력되어야 하는 값이다. 결론은 오름차순된 index와 처음 index를 비교하여 가장 왼쪽으로 이동한 수를 찾으면 된다.

 

내 코드

python 3에서는 시간 초과가 났지만 pypy3에서는 시간 초과가 안 났다.

찾아봤더니 pypy3는 자주 사용되는 코드를 캐싱하는 기능이 있어 복잡한 코드에서는 pypy3가 유리하다.

python3는 간단한 코드에서 속도와 메모리가 유리하다.

더 알고 싶다면 밑에 내용을 참고하길 바란다.

https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4

Python3 와 PyPy3 차이

 

위 코드는 python3에서 시간 초과가 나지 않고 돌아갔다.

우선 내 코드와 차이점은 dictionary를 사용하지 않았고 sys.stdin.readline을 사용했다.

그리고 Max 변수를 사용하여서 sort된 값에서 원래 index를 뺐을 때 가장 큰 값을 바로 구했다.

위 내 코드와 비교했을 때  간단하고 메모리도 더 적게 사용하였고, 시간도 빨랐다.