정렬 백준 연습문제 풀이 (JAVA) - (백준 2751, 15688, 11652, 5648, 1181, 2910, 7795

이요환·2022년 9월 5일
Java백준알고리즘정렬
0

알고리즘

목록 보기
16/20

처음

지난 공부에 이어 정렬과 관련된 백준 연습 문제들을 풀었다.

중간

1. 백준 2751 - 수 정렬하기 2


n의 개수가 최대 백만이고, 정수의 범위도 200만 개이기 때문에, 기본적인 O(N^2) 정렬을 사용할 수 없었다. 이전 포스팅에서 구현했던 merge sort의 동작을 테스트할 겸 이 문제에 적용해봤다.

package sort;

import java.io.*;
import java.util.Arrays;


//+stable sort!!!!
public class BOJ2751 {
    static int[] test;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());


        test = new int[n];

        for (int i = 0; i < n; i++) {
            test[i] = Integer.parseInt(br.readLine());
        }


        mergeSort(0, test.length);

        for (int x : test) {
            bw.write(x +"");
            bw.newLine();
        }
        bw.close();
    }

    //en-st==2 일 때 st~mid, mid~en이 각각 하나씩 언소를 가진당

    //st~mid, mid~en이 각각 정렬되어있을 때 증렬~
    private static void merge(int st, int en) {
        int mid = (st + en) / 2;
        int pf = 0;
        int pb = 0;

        int[] front = Arrays.copyOfRange(test, st, mid);
        int[] back = Arrays.copyOfRange(test, mid, en);

        for (int i = 0; i < en - st; i++) {
            if (pf >= front.length) test[st + pf + pb] = back[pb++];
            else if (pb >= back.length) test[st + pf + pb] = front[pf++];
            else if (front[pf] < back[pb]) test[st + pf + pb] = front[pf++]; //이렇게 하면 stable Sort가 아니게 된다. 같을 때도 front를 먼저 보내줘야댐!!
            else test[st + pf + pb] = back[pb++];
        }
    }

    private static void mergeSort(int st, int en) {
        if (en - st == 1) return;
        int mid = (st + en) / 2;

        mergeSort(st, mid);
        mergeSort(mid, en);
        merge(st, en);
    }

}

Arrays.sort()를 사용해도 통과했을 것이다.

2. 백준 15688 - 수 정렬하기 5


이번 문제는 countingSort를 활용해서 풀어봤다. n 값의 범위가 충분히 작았기 때문에 counting sort 활용이 가능했다.

package sort;


import java.io.*;

//counting sort 대상이되는 수의 범위가 적을 때 범위크기의 배열을 만들어서 다넣음 -> 배열 단원에서 활용한 개념 그대로 이용
//comparison, non comparison 정렬의 차이 확인
public class BOJ15688 {
    static int n;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        countingSort(arr);
        bw.close();
    }

    private static void countingSort(int[] arr) throws IOException {
        int[] nNums = new int[2000001];

        for (int i = 0; i < n; i++) {
            nNums[arr[i]+1000000]++;
        }

        for (int i = 0; i < nNums.length; i++) {
            for (int j = 0; j < nNums[i]; j++) {
                bw.write((i - 1000000 + ""));
                bw.newLine();
            }
        }
    }
}

counting sort의 개념은 배열 단원에서 이용했던 아이디어와 같다. n의 범위만큼 크기를 갖는 배열을 만들어, 해당 숫자가 얼마나 등장하는 지 저장한 후, 출력한다. O(n+k)의 시간복잡도를 갖지만, 수의 범위가 충분히 작아야한다. 대충 10,000,000 이하일 때 가능하다고 한다.

3. 백준 11652 - 카드

map을 활용하면 아주 쉽게 해결할 수 있는 문제다. key, value 쌍을 n과 n의 개수로 정해서 저장하면 되기 때문이다.

package sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class BOJ11652 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());

        Map<Long, Long> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            long tmp = Long.parseLong(br.readLine());
            map.put(tmp, map.getOrDefault(tmp, (long) 0) + 1);
        }

        long answer = Integer.MIN_VALUE; //key 값
        long maxN = -1; //값

        for (long x : map.keySet()) {
            long tmp = map.get(x); //현재 개수, x는 키

            if (tmp == maxN && x < answer) answer = x;
            else if (tmp > maxN) {
                maxN = tmp;
                answer = x;
            }
        }
        System.out.println(answer);
    }
}

counting sort를 쓰지 못하게 하기 위해서인지 n의 범위가 2^62까지 있었다. 그래서 long 자료형을 써야 했다.

정렬을 활용한다면, 오름차순 정렬을 한 뒤 같은 수가 얼마나 반복되는 지를 활용하는 방식을 써도 될 것 같다는 생각을 했다.

4. 백준 5648 - 역원소 정렬

이 문제는 radix sort를 활용해서 해결했다. radix sort를 거꾸로 적용하면 될 것이라고 생각했는데, 앞쪽의 0을 처리하는 과정은 어차피 해야하기 때문에, 그냥 뒤집은 뒤에 정렬했다.

package sort;


import java.io.*;
import java.util.*;

//radix sort 활용
public class BOJ5648 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(sc.next());
        long[] arr = new long[n];

        for (int i = 0; i < n; i++) {
            arr[i] = reverseNum(sc.next());
        }
        Arrays.sort(arr);
        for (long x : arr) {
            bw.write(x + " ");
        }
        bw.close();
    }

    private static long reverseNum(String str) {
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = chars.length -1; i >= 0 ; i--) {
            sb.append(chars[i]);
        }
        return Long.parseLong(sb.toString());
    }

    private static void reverseRadix(long[] arr) {
        List<Long>[] list = new List[10];
        for (int i = 0; i < list.length; i++) {
            list[i] = new ArrayList<>();
        }
        int n = 10;

        for (int i = 0; i < 13; i++) {
            for (long x : arr) {
                list[(int) x % n / (n / 10)].add(x);
            }

            int cnt = 0;

            for (List<Long> x : list) {
                for (long y : x) {
                    arr[cnt++] = y;
                }
                x.clear();
            }
            n = n*10;
        }
    }

}

radixsort 함수는 구현해놓고 사용하질 않았다. 그리고 이유가 뭔지 전혀 모르겠는데 문제의 입력방식이 이상해서 오랜만에 Scanner를 이용해서 입력받았다.

입력받은 숫자를 문자 배열로 바꾼 뒤, stringBuilder로 역순으로 입력받은 뒤 long으로 변경하는 방식으로 숫자를 뒤집었다.

5. 백준 1181 - 단어 정렬

문자열을 정렬하는 데, 정렬 기준이 자바 문자열 비교 기준과는 다른 경우였다. 이 문제는 comparator를 새로 정의해서 해결했다.

package sort;

import java.io.*;
import java.util.*;

public class BOJ1181 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());

        Set<String> set = new HashSet<>();


        for (int i = 0; i < n; i++) {
            set.add(br.readLine());
        }

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

        for (String x : list) {
            bw.write(x);
            bw.newLine();
        }
        bw.close();
    }
}

set을 활용해서 중복 원소를 없앴다. comparator는 길이를 기준으로 비교하되, 길이가 같을 때는 기존의 문자열의 compareTo()로 비교하도록 했다. (사전 기준 정렬)

6. 백준 2910 - 빈도 정렬

많이 나온 숫자대로 정렬해야하고, 등장하는 횟수가 같을 땐, 기존의 순서를 유지해야 한다. (stable sort!!!!) 정렬에서 자료구조 활용을 공부하게 된 문제였다.

우선 각 원소의 개수를 저장하는 데는 map을 사용했는데, stable sort를 하기 위해서는 순서를 저장할 필요가 있었기 때문에 LinkedHashMap을 활용했다. 원소 검색을 할 필요는 없었기 때문에 시간복잡도에서 별로 손해볼 일은 없다.

저번 포스팅에서 공부했듯이, 컬렉션에서의 sort()는 stable하기 때문에, 이것을 이용했다. 다만, 등장 횟수인 map의 value를 기준으로 비교해야하기 때문에 comparator를 구현했다.

public class BOJ2910 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Map<Integer, Integer> map = new LinkedHashMap<>();

        for (int i = 0; i < n; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            map.put(tmp, map.getOrDefault(tmp, 0)+1);
        }

        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());

        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });

        Iterator<Map.Entry<Integer,Integer>> iter = list.iterator();
        StringBuilder sb = new StringBuilder();
        while (iter.hasNext()) {
            Map.Entry<Integer, Integer> tmp = iter.next();

            for (int i = 0; i < tmp.getValue(); i++) {
                sb.append(tmp.getKey()).append(" ");
            }
        }
        System.out.println(sb);
    }
}

LinkedHashMap 자료구조에 대한 정보는 이 블로그에서 아이디어를 얻었다.

7. 백준 7795 - 먹을 것인가 먹힐 것인가

정렬을 활용하지 않는다면 시간복잡도가 O(NM)이다. 정렬을 활용한 방법은 다음과 같다.

  1. 두 배열을 오름차순으로 정렬한 후, arrA와 arrB를 검사하는 포인터를 이용해 검사한다.
  2. arrA[idxA]와 arrB[idxB]를 비교한다.
    2-1. 전자가 클 경우, idxA 이후의 원소들도 모두 해당 B를 먹을 수 있는 것이므로, arrA.length - idxA 만큼 cnt를 증가시키고, idxB++
    2-2. 그렇지 않을 경우, idxA++
package sort;

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

public class BOJ7795 {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            int[] arrA = new int[n];
            int[] arrB = new int[m];

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arrA[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arrB[j] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(arrA);
            Arrays.sort(arrB);

            int idxA = 0;
            int idxB = 0;
            int cnt = 0;
            while (idxA < n && idxB < m) {
                if (arrA[idxA] > arrB[idxB]) {
                    cnt += arrA.length - idxA;
                    idxB++;
                } else {
                    idxA++;
                }
            }
            System.out.println(cnt);
        }
    }

}

끝

정렬과 관련된 기본적인 문제들을 풀어봤다. 몇 알고리즘을 공부하고 문제들을 풀어 본 뒤 느낀 것은, 정렬 알고리즘 개념을 비롯해서 자바의 내장 함수들이 어떤 특성을 갖고 있는 지 잘 이해해야할 것 같다. 그리고 정렬 관련 문제들은 자료구조가 중요한 경우도 많은 것 같다. 그 외에도 comparable 인터페이스와 comparator 에 대해서도 잘 이해하고 있어야할 것 같다.

연습문제 출처 : encrypted-def github

profile
이요환
컴퓨터 사이언스, 알고리즘, 모든 애플리케이션에 관심이 있습니다.
이전 포스트

병합 정렬 (Merge Sort), 퀵 정렬 (Quick Sort) (JAVA) 개념

다음 포스트

다이나믹 프로그래밍 (Dynamic Programming) 개념 및 연습 문제 풀이 (JAVA) - (백준 1463 9095 2579 1149 11726 11659 12852)

0개의 댓글