22번

bubbleSort(거품정렬) 문제였다.

처음 for문을 이용해 i<arr.length만큼 반복을 수행해주고,
두번 째 for문을 이용해 j<arr.length-j-1만큼 요소 값을 비교해준다.
if문을 사용해 arr[j]>arr[j+1]일 때, 임시변수 temp에 arr[j]을 넣어주고, arr[j]=arr[j+1], arr[j+1]=temp 을 각각 넣어줬다. 마지막으로 변환한 arr을 반환해주었는데, 실행 시간 초과가 뜬다... 🤯

왜 실행 시간 초과가 뜨는지 문제를 파악하고 구글을 뒤져보다 첫 번째 for문에 int temp=0을 미리 선언해주고, 위와 동일하게 j반복문을 돌린 후, j반복문을 나왔을 때 if(temp==0) break를 추가해주니 테스트가 완료됐다.

문제의 Advanced에 "위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다."라고 명시되어 있는데,
아마 요소가 바뀌지 않았을 때(배열이 이미 정렬된 상태일 때) break를 통해 빠져나옴으로써 보다 수행시간을 단축하라는 테스트 케이스가 있었던 것으로 판단된다.