[BOJ] 13단계 정렬

kinggora 2023. 4. 6. 20:46

2750

시간 복잡도가 O(n²)인 정렬 알고리즘: 삽입 정렬, 선택 정렬, 버블 정렬

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(reader.readLine());
        }

        //삽입 정렬
        int[] arr1 = arr.clone();
        for(int i = 1; i < N; i++) {
            int key = i;
            for(int j = i - 1; j >= 0; j--) {
                if(arr1[j] > arr1[key]) {
                    swap(arr1, j, key);
                    key = j;
                }
            }
        }

        //선택 정렬
        int[] arr2 = arr.clone();
        for(int i = 0; i < N-1; i++) {
            int min = i;
            for(int j = i + 1; j < N; j++) {
                if(arr2[min] > arr2[j]) {
                    min = j;
                }
            }
            if(min != i) {
                swap(arr2, min, i);
            }
        }

        //버블 정렬
        int[] arr3 = arr.clone();
        for(int i = N - 1; i > 0; i--) {
            for(int j = 0; j < i; j++) {
                if(arr3[j] > arr3[j+1]) {
                    swap(arr3, j, j+1);
                }
            }
        }
        printArray(arr3);
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    static void printArray(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

*시간 복잡도가 O(n^2)인 정렬 알고리즘: 삽입 정렬, 선택 정렬, 버블 정렬

*오름차순 정렬: Arrays.sort() 사용 가능

*버블 정렬은 한 라운드당 가장 큰 값이 맨 뒤로 이동하는 것이 보장되므로 마지막 원소는 비교 연산에서 제외함

2587

대표값2

평균과 중앙값

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = new int[5];

        int sum = 0;
        for (int i = 0; i < 5; i++) {
            arr[i] = Integer.parseInt(reader.readLine());
            sum += arr[i];
        }
        Arrays.sort(arr);
        System.out.println(sum / arr.length);
        System.out.println(arr[arr.length / 2]);
    }
}

25305

커트라인

k번째로 큰 수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());

        tokenizer = new StringTokenizer(reader.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(arr);
        System.out.println(arr[arr.length - k]);
    }
}

2751

수 정렬하기 2

시간 복잡도가 O(nlogn)인 정렬 알고리즘: 병합 정렬, 힙 정렬 등

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            list.add(Integer.parseInt(reader.readLine()));
        }
        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        for(int num : list) {
            sb.append(num).append("\n");
        }
        System.out.println(sb);
    }
}

*Arrays.sort() : Dual-pivot Quicksort 사용 => O(nlogn)~O(n^2)

*Collections.sort(): Timsort (merge sort + insection sort) 사용 => O(n)~O(nlogn)

*리스트 요소를 출력하기 위해 매번 System.out.println() 호출하자 시간 초과가 남 -> StringBuilder 로 한 번에 출력

10989

수 정렬하기 3

수의 범위가 작다면 카운팅 정렬 사용 (1~10000)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] cnt = new int[10001];

        for(int i = 0; i < N; i++) {
            cnt[Integer.parseInt(reader.readLine())]++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < cnt.length; i++) {
            for(int j = 0; j < cnt[i]; j++) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }
}

*입력 숫자의 중복이 가능하기 때문에 cnt 만큼 출력하도록 함

1427

소트인사이드

숫자 문자열, 내림차 정렬

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = reader.readLine();
        int[] cnt = new int[10];
        for(int i = 0; i < str.length(); i++) {
            cnt[str.charAt(i) - '0']++;
        }

        for(int i = cnt.length - 1; i >= 0; i--) {
            for(int j = 0; j < cnt[i]; j++) {
                System.out.print(i);
            }
        }
    }
}

11650

좌표 정렬하기

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 reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[][] arr = new int[N][2];

        StringTokenizer tokenizer;
        for(int i = 0; i < N; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            arr[i][0] = Integer.parseInt(tokenizer.nextToken());
            arr[i][1] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o2[0];
                }
            }
        });

        for(int i = 0; i < N; i++) {
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }
}

*Arrays.sort() 의 Comparator 를 오버라이딩하여 2차원 배열을 비교할 수 있도록 함

* Comparator.compare(Object o1, Object o2) *

o1 < o2 => 음수 반환. o1, o2 순서 그대로

o1 == o2 => 0 반환

o1 > o2 => 양수 반환. o1, o2 순서 바꿈

ex. 오름차순

compare(1, 3) -> 음수 반환해야 함

compare(3, 1) -> 양수 반환해야 함

return o1 - o2

ex. 내림차순

compare(1, 3) -> 양수 반환해야 함

compare(3, 1) -> 음수 반환해야 함

return o2 - o1

11651

좌표 정렬하기 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 reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[][] arr = new int[N][2];

        for(int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            arr[i][0] = Integer.parseInt(tokenizer.nextToken());
            arr[i][1] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(arr, (o1, o2) -> {
            if(o1[1] == o2[1]) {
                return o1[0] - o2[0];
            } else {
                return o1[1] - o2[1];
            }
        });

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            sb.append(arr[i][0] + " " + arr[i][1]).append("\n");
        }
        System.out.print(sb);
    }
}

*Arrays.sort() 의 Comparator 오버라이딩에 람다식 사용

1181

단어 정렬

길이가 짧은 것부터
길이가 같으면 사전 순으로
중복 단어 제거

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        List<String> list = new ArrayList<>();

        for(int i = 0; i < N; i++) {
            String str = reader.readLine();
            if(!list.contains(str)){
                list.add(str);
            }
        }

        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length() == o2.length()) {
                    return o1.compareTo(o2);
                } else {
                    return o1.length() - o2.length();
                }
            }
        });

        for(String s : list) {
            System.out.println(s);
        }
    }
}

*Collections.sort() 의 Comparator 오버라이딩

*중복 제거를 위해 List 대신 Set을 사용해도 됨. 대신 Collections.sort() 를 사용하기 위해서는 List로 변환해줘야 함

10814

나이순 정렬

안정 정렬(stable sort): 값이 같은 원소의 전후관계가 바뀌지 않는 정렬 알고리즘

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 reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        String[][] arr = new String[N][2];

        for(int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            arr[i][0] = tokenizer.nextToken();
            arr[i][1] = tokenizer.nextToken();
        }

        Arrays.sort(arr, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
            }
        });

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            sb.append(arr[i][0] + " " + arr[i][1]).append("\n");
        }
        System.out.print(sb);
    }
}

*Arrays.sort() 의 Comparator 오버라이딩: 0번째 요소만 비교하여 1번째 요소는 들어온 순서대로 유지되도록

18870

좌표 압축

O(n)으로 index를 접근하면 시간 초과가 발생함

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 reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[] arr = new int[N];

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }

        int[] sortedArr = arr.clone();
        Arrays.sort(sortedArr);

        HashMap<Integer, Integer> rankMap = new HashMap<>();
        int rank = 0;
        for(int i = 0; i < sortedArr.length; i++) {
            if(!rankMap.containsKey(sortedArr[i])) {
                rankMap.put(sortedArr[i], rank);
                rank++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++) {
            sb.append(rankMap.get(arr[i])).append(" ");
        }
        System.out.print(sb);
    }
}