[백준] 2750 수 정렬하기

최근 정렬 알고리즘 공부를 하고 있겠다.. 간단한 정렬 문제를 시도했다.

계수정렬로 시도해볼까 하다가, 단순히 연결되는 수에 대한 정렬이 아니라 임의로 들어오는 수들에 대해서 정렬을 해야해서 그냥 일반적인 정렬로 풀었다.

중간에 ‘수는 중복되지 않는다’ 라는 말을 중복된 수는 제거하라는 말인줄 알아서.. 중복을 제거하는 걸 고민했었더랬다…

Python

사실 아래처럼 푸는 거보다 그냥 sort 메소드가 있는 패키지를 이용하는게 빠르긴 하다. 그냥 정렬 구현을 위해 풀어봤다.

N = int(input())
T = set([])
data = []

def dataSort(a, b):
    if(data[a] > data[b]):
        temp = data[a]
        data[a] = data[b]
        data[b] = temp

for i in range(N):
    T.add(int(input()))
    data = list(T)

for i in range(1, N):
    for j in range(len(data) - i):
        dataSort(j, j + 1)

for i in range(len(data)):
    print(data[i])

Java

아래는 중복을 고려하지 않고 문제를 풀었던 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] T = new int[n];

        for (int i = 0; i < n; i++) {
            T[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            for (int j = i; j < T.length; j++) {
                sorting(T, i, j);
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println(T[i]);
        }
    }
    
    public static void sorting(int[] array, int a, int b) {
        if (array[a] > array[b]) {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
        }
    }
}

중복을 고려했을 때는 내가 온전히 구현하기는 좀 어려워보여서 그냥 패키지를 이용했다. Set과 ArrayList를 이용하고, 정렬을 위한 comparator 클래스를 하나 구현했다.

import java.util.Scanner;

public class Main {
		public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList T = new ArrayList();

        for (int i = 0; i < n; i++) {
            T.add(i, sc.nextInt());
        }

        Set<Integer> uniqueT = new HashSet<>(T);
        ArrayList<Integer> answer = new ArrayList<>(uniqueT);

        answer.sort(new DescendingComparator());

        for (Integer num : answer) {
            System.out.println(num);
        }
    }

    public static class DescendingComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }
    }
}

사실 이 문제는 아래처럼 간단히도 가능하다. 그냥 Arrays.sort 메소드 써버리면 된다. (앗, 여기도 중복은 고려 안한 코드네)

import java.util.Scanner;

public class Main {
		public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] T = new int[n];

        for (int i = 0; i < n; i++) {
            T[i] = sc.nextInt();
        }

        Arrays.sort(T);

        for (int i = 0; i < n; i++) {
            System.out.println(T[i]);
        }
    }
}

 

부족함이 많아서 간단한 문제들부터 풀어보고 있다.
알고리즘을 공부해도 역시 문제를 풀 때는 그걸 구현해내는게 아직 많이 미숙한 거 같다.