[Baekjoon] #23968 알고리즘 수업 - 버블 정렬1
📝 문제
https://www.acmicpc.net/problem/23968
💡 풀이 방법
💬 아이디어
버블 정렬의 기본적인 개념을 이용한다.
먼저, 원소가 교환되는 과정을 살펴보기 위해 교환 횟수를 의미하는 변수 cnt
를 선언하고, 정답으로 출력된 answer
를 선언한다.
다음으로 배열의 원소 개수만큼 루프문을 실행하여 배열 내의 연속한 값들의 크기를 비교한다. 두 개의 원소가 크기의 내림차순으로 존재한다면, 자리를 상호 교환하고 cnt
에 1을 더해준다. cnt
가 교환 횟수 K
와 같아졌을 때 마지막으로 자리를 교환한 두 값을 answer
에 저장한다.
💬 알고리즘
- 배열 A의 길이
N
, 교환 횟수K
, 배열 A의 원소를 각각sys.stdin.readline()
을 통해 입력받는다. - 배열 A의
i
번째 원소와i+1
번째 원소를 비교하여 크기가 작은 원소가 앞쪽에 오도록 자리를 교환하고cnt
에 1을 더해준다. - 정렬된 원소를 제외한 채 위의 과정을 반복한다.
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
💻 소스코드
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
Author And Source
이 문제에 관하여([Baekjoon] #23968 알고리즘 수업 - 버블 정렬1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seongmini/Baekjoon-23968-알고리즘-수업-버블-정렬1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)