[Algorithm] 선택 정렬

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ 정렬

정의

- 데이터를 특정한 기준에 따라 순서대로 나열하는 것

- 일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다

---

✨ 선택 정렬

정의

- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬

- 이중 반복문을 사용해 가장 작은 원소 확인 -> 데이터 교환의 과정을 반복한다

시간 복잡도

- N번 만큼 가장 작은 수를 찾아 맨 앞으로 보내야 하므로 O(N^2) 만큼의 시간이 소요된다

- N + (N-1) + (N-2) + ... + 2 => (N^2 + N - 2) / 2

---

✨ 문제

- 선택 정렬을 사용하지 않지만...

접근

- 좌표 Xi보다 작은 값이 몇 개 있는지 구하기

1차 시도

- HashSet으로 중복 값 제거 + 오름차순으로 만들어준 후 인덱스 값을 가져오려고 했다

- 그러나 좌표 압축 부분에서 시간 초과로 실패. 나머지는 O(N)의 시간 복잡도를 유지한 반면, 좌표 압축 부분에서 이중 for문으로 O(N^2)의 시간 복잡도를...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 배열에 넣기
        for (int i=0; i<N; i++) {
            arr[i]= Integer.parseInt(st.nextToken());
        }

        HashSet<Integer> hashSet = new HashSet<>();

        for (int i : arr) {
            hashSet.add(i);
        }
        System.out.println(hashSet);

        // 정렬
        ArrayList<Integer> arrayList = new ArrayList<>(hashSet);
        Collections.sort(arrayList);

        // 좌표 압축
        for (int i=0; i<N; i++) {
            for (int j=0; j<arrayList.size(); j++) {
                if (arr[i] == arrayList.get(j)) {
                     sb.append(j).append(" ");
                }
            }
        }

        System.out.println(sb);
    }
}

 

2차 시도

- 좌표 압축 부분에서 문제가 있다는 사실을 깨닫고 다른 분들의 코드를 참고하던 중, HashSet에는 get()이 없어 HashMap을 쓰는게 더 낫다는 것을 깨달았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        int[] sortedArr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 배열에 넣기
        for (int i=0; i<N; i++) {
            arr[i] = sortedArr[i] = Integer.parseInt(st.nextToken());
        }

        // 배열 정렬
        Arrays.sort(sortedArr);
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        int index = 0;
        for (int i : sortedArr) {
            // 중복 값 제거
            if (!hashMap.containsKey(i)) {
                hashMap.put(i, index);
                index++;
            }
        }

        for (int k : arr) {
            int idx = hashMap.get(k); // 원본 배열 원소(key)에 대한 인덱스 값(value)을 가져온다
            sb.append(idx).append(" ");
        }

        System.out.println(sb);
    }
}

 

성공!