🤡 선택 정렬

🤠 문제

🤠 풀이

😇 어떻게 문제를 풀 것인가?

강의 듣기 전

• 입력값으로 N을 입력받는다.
• 공백을 두고 숫자를 입력한다.
• for문을 이용해 정렬한다.
• 2중 for문을 이용하면 시간 복잡도는 O(N^2)이 된다.

---

강의 듣고 난 후

• i,j를이용해 2중 for문을 만든다.
• idx라는 변수를 이용해 검사하는 횟수를 줄일 수 있다.
• arr[i]는 검사하는 것들 중 가장 작은 값을 넣어준다.
  

for(int i=0;i<n-1;i++){
            int idx = i;
            for(int j=i+1;j<n;j++){
                if(arr[j] < arr[idx])
                    idx=j;
            }
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
        return arr;

🤠 소스코드

package algolecture;
import java.io.IOException;
import java.util.Scanner;

public class Main44 {
    public int[] solution (int n, int[] arr){
        for(int i=0;i<n-1;i++){
            int idx = i;
            for(int j=i+1;j<n;j++){
                if(arr[j] < arr[idx])
                    idx=j;
            }
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
        return arr;
    }
    
    public static void main(String[] args) throws IOException {
        Main44 T = new Main44();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = kb.nextInt();
        }
        for(int x : T.solution(n, arr))
            System.out.print(x + " ");
    }
}