sort()
함수 사용하면 쉽게 끝날 문제지만, 정렬을 직접 구현해보자!
버블정렬
참고
두 인접한 데이터의 크기를 비교해 정렬하는 방법.
인접한 데이터간 swap 연산을 통해 정렬
생각한 풀이
마지막 교환이 일어난 위치를 활용한 방법(참고)
import java.util.Scanner;
public class Practice15 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
for(int i=0; i<arr.length-1; i++) {
int lastSwap = 0; // 교환이 일어난 마지막 위치
for(int j=arr.length-1; j>i; j--) {
if(arr[j] < arr[j-1]) {
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] =tmp;
lastSwap = j-1; // 교환이 일어난 위치 최신
}
}
i = lastSwap; // 교환이 일어난 마지막 위치 i에 삽입
}
for (int i = 0; i < N; i++) {
System.out.println(arr[i]);
}
sc.close();
}
}
난 내가 해낸 줄 알았음
근데 놀랍게도 시간초과... 짱나네..?
그래서 그냥 책에 있는대로 그냥 현재 배열 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수를 바꾸도록 코드를 변경함.
import java.util.Scanner;
public class Practice15 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
// 변경한 코드
for(int i=0; i<arr.length-1; i++) {
for(int j=0; j<arr.length-1-i; j++) {
if(arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] =tmp;
}
}
}
for (int i = 0; i < N; i++) {
System.out.println(arr[i]);
}
sc.close();
}
}
훨씬 간결해졌다.
그리고 통과했다.
내가 생각한 풀이가 시간초과로 실패하면 기분이 더럽다는걸 이번에 깨달았음..