[이코테] 정렬(Sort)

정렬

• 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용되며, 가장 많이 사용되는 알고리즘 중 하나이다.

---

예제 1) 위에서 아래로

다양한 수로 이루어진 하나의 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

 

문제 해설

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

public class Main {

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

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

        Arrays.sort(array, Collections.reverseOrder());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(array[i] + " ");
        }

        System.out.println(sb);
    }
}

 

 

 

 

예제 2) 성적이 낮은 순서로 학생 출력하기

N명의 학생 정보(학생의 이름, 학생의 성적)가 주어졌을 때, 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

 

문제 해설

• Comparable의 compareTo 메서드로 학생의 성적을 기준으로 정해서 성적이 낮은 순서대로(오름차순) 정렬한다.

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

class Student implements Comparable<Student>{
    String name;
    int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return this.name;
    }

    public int getScore() {
        return this.score;
    }

    //성적이 낮은 순서대로 정렬(오름차순)
    @Override
    public int compareTo(Student other) {
        return this.score - other.score;
    }
}

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());    //학생 수

        List<Student> students = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            int score = Integer.parseInt(st.nextToken());

            students.add(new Student(name, score));
        }

        Collections.sort(students);

        for (int i = 0; i < students.size(); i++) {
            System.out.print(students.get(i).getName() + " ");
        }
    }
}

 

 

 

예제 3) 두 배열의 원소 교체

N개의 자연수인 원소로 구성된 배열 A와 B가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A 중에서 모든 원소의 합이 최대가 되도록 프로그램을 작성하시오. 바뀌치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소를 서로 바꾸는 것을 말한다.

 

문제 해설

• 배열 A의 모든 원소의 합이 최대가 되도록 하려면, 배열 A의 가장 작은 수와 배열 B의 가장 큰 수를 교체한다.
• 배열 A는 오름차순, 배열 B는 내림차순 정렬한 후, 첫 번째 인덱스부터 비교한다.
• 이 때, (배열 A의 원소) < (배열 B의 원소) 일 때에만 교체한다.

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

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   //원소 개수
        int k = Integer.parseInt(st.nextToken());   //바꿔치기 연산 횟수

        Integer[] arrayA = new Integer[n];
        Integer[] arrayB = new Integer[n];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arrayA[i] = Integer.parseInt(st1.nextToken());
            arrayB[i] = Integer.parseInt(st2.nextToken());
        }

        Arrays.sort(arrayA);    //배열A 오름차순 정렬
        Arrays.sort(arrayB, Collections.reverseOrder());    //배열B 내림차순 정렬

        for (int i = 0; i < k; i++) {
            if (arrayA[i] < arrayB[i]) {    //배열A의 원소가 배열B의 원소보다 작을 때만 바꿔치기 수행
                int temp = arrayA[i];
                arrayA[i] = arrayB[i];
                arrayB[i] = temp;
            } else {
                break;
            }
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arrayA[i];
        }

        System.out.println(sum);
    }
}

---

[참고]

이것이 취업을 위한 코딩 테스트다 with 파이썬