[Baekjoon] #23968 알고리즘 수업 - 버블 정렬1

📝 문제

https://www.acmicpc.net/problem/23968

💬 풀이 방법

아이디어

버블 정렬의 기본적인 개념을 이용한다.

먼저, 원소가 교환되는 과정을 살펴보기 위해 교환 횟수를 의미하는 변수 cnt를 선언하고, 정답으로 출력된 answer를 선언한다.
다음으로 배열의 원소 개수만큼 루프문을 실행하여 배열 내의 연속한 값들의 크기를 비교한다. 두 개의 원소가 크기의 내림차순으로 존재한다면, 자리를 상호 교환하고 cnt에 1을 더해준다. cnt가 교환 횟수 K와 같아졌을 때 마지막으로 자리를 교환한 두 값을 answer에 저장한다.

알고리즘

1. 배열 A의 길이 N, 교환 횟수 K, 배열 A의 원소를 각각 sys.stdin.readline()을 통해 입력받는다.
2. 배열 A의 i번째 원소와 i+1번째 원소를 비교하여 크기가 작은 원소가 앞쪽에 오도록 자리를 교환하고 cnt에 1을 더해준다.
3. 정렬된 원소를 제외한 채 위의 과정을 반복한다.
4. cnt 가 K와 같아졌을 때, 마지막으로 교환된 두 개의 원소를 변수 answer에 저장한다.
   
   

--

⏱ 시간 초과 오류

코드를 실행했을 때, 시간 초과 오류가 발생하여 수행 시간을 줄일 수 있는 다양한 방법을 모색해보았다.

1. input() vs sys.stdin.readline()

일반적으로 sys 모듈의 sys.stdin.readline()이 input()을 활용한 입력 방식보다 빠르다. 이유를 알아보기 위해 두 메소드의 차이점을 살펴보도록 하자.

먼저, input()은 prompt message를 인자로 받을 수 있기 때문에 경우에 따라 출력하는 데에 추가적으로 소요되는 시간이 발생한다. 반면, sys.stdin.readline()은 prompt message를 인수로 받지 않는다.

다음으로, input()은 입력받은 값의 개행 문자를 삭제하여 리턴한다. 이 과정에서 추가적인 시간이 소모되는 반면, sys.stdin.readline()은 개행 문자를 포함한 값을 리턴하기 때문에 추가적으로 시간이 소모되지 않는다.

2. Python3 vs PyPy3

반복이 많은 코드는 PyPy3를 활용하는 것이 효율적이다.
Python3 vs PyPy3

💻 소스코드

import sys

n, k = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

count = 0
answer = -1

for i in range(n-1, 0, -1):
	for j in range(i):
		if nums[j] > nums[j+1]:
			count += 1
			nums[j], nums[j+1] = nums[j+1], nums[j]

			if count == k:
				answer = f'{nums[j]} {nums[j+1]}'	

print(answer)

--

참고 사이트

🙇🏻‍♂️ https://buyandpray.tistory.com/7