[이코테] 정렬 - 위에서 아래로, 성적이 낮은 순서로 학생 출력하기, 두 배열의 원소 교체(Java)

 

 

 

 

크게 분석할 만한 것도 없고 상당히 쉽기 때문에 한꺼번에 올린다. 이렇게 표시된 조건만 잘 확인하면 된다.

또한 아직 자바에 미숙한지라 관련 내용도 간략하게 정리하였으니 참고하고 싶으신 분은 보면 좋을 것 같다.

 

 

 

 

---

 

 

 

 

위에서 아래로

 

 

 

 

문제

 

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수 부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

 

 

 

 

입력 조건

 

• 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1<=N<=500)
• 둘째 줄부터 N+1번째 줄까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다.

 

 

 

 

출력 조건

 

• 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다.

 

 

 

 

분석

입력 조건을 살펴보면 N이 500 이하이므로 O(N^2) 시간 복잡도를 가져도 상관없다. 또한 출력 조건에서 stable sort가 지켜지지 않아도 된다는 점을 알 수 있다. 결론적으로 어떠한 정렬 알고리즘을 사용하여도 상관 없다. 그래서 나는 간편하게 자바에 내장된 정렬 함수 Arrays.sort()를 이용하였다.

 

참고로 Arrays.sort()는 DualPivotQuicksort 방식을 사용하며 시간 복잡도는 평균 O(NlogN), 최악 O(N^2)이다.

 

 

 

 

Java 코드

 

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

public class Main {

    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());

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

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

        for (int i= 0; i < n; i++) {
            bw.write(arr[i] + " ");
        }

        br.close();
        bw.close();
    }
}

 

 

 

 

---

 

 

 

 

 

성적이 낮은 순서로 학생 출력하기

 

 

 

 

문제

 

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

 

 

 

 

입력 조건

 

• 첫 번재 줄에 학생의 수 N이 입력된다. (1<=N<=100,000)
• 두 번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

 

 

 

 

출력 조건

 

• 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

 

 

 

 

풀이 과정 & 분석

 

아직 자바 애송이인 나는 comparator과 comparable에 미숙하다 ^^..(강해지자 예림아..) 이번 기회에 확실히 알고 넘어가자. 따로 포스트를 올릴까도 생각했지만 상당히 잘 정리해놓은 포스트가 있다. 아래 링크를 참고하면 된다.

 

자바 [JAVA] - Comparable 과 Comparator의 이해

 

문제 자체는 쉽다. 입력 조건을 보면 N이 100,000 이하이므로 시간 복잡도가 O(NlogN) 이하인 정렬을 사용하여야 한다. 그래서 나는 간편하게 자바에 내장된 정렬 함수 Collections.sort()를 사용하였다.

 

참고로 Collections.sort()는 TimeSort 방식(삽입정렬+합병정렬)을 사용하며 시간 복잡도는 평균, 최악 모두 O(NlogN)이다.

 

 

 

 

Java 코드

 

// comparator 사용
import java.util.*;
import java.io.*;


public class Main {

    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());

        List<Student> students = new ArrayList<>();
        StringTokenizer st;
        String name;
        int score;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            name = st.nextToken();
            score = Integer.parseInt(st.nextToken());
            students.add(new Student(name, score));
        }

        Collections.sort(students, comparator);

        for (int i = 0; i < n; i++) {
            bw.write(students.get(i).getName() + " ");
        }

        br.close();
        bw.close();
    }

    static Comparator<Student> comparator = new Comparator<Student>() {
        @Override
        public int compare(Student o1, Student o2) {
            return o1.getScore() - o2.getScore();
        }
    };
}

public class Student {

    private String name;
    private int score;

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

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }
}

 

// Comparable 사용
import java.util.*;
import java.io.*;


public class Main {

    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());

        List<Student> students = new ArrayList<>();
        StringTokenizer st;
        String name;
        int score;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            name = st.nextToken();
            score = Integer.parseInt(st.nextToken());
            students.add(new Student(name, score));
        }

        Collections.sort(students);

        for (int i = 0; i < n; i++) {
            bw.write(students.get(i).getName() + " ");
        }

        br.close();
        bw.close();
    }
}

public class Student implements Comparable<Student> {

    private String name;
    private int score;

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

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }

    @Override
    public int compareTo(Student o) {
        return this.score - o.score;
    }
}

 

 

 

 

---

 

 

 

 

두 배열의 원소 교체

 

 

 

 

문제

 

동빈이는 두 개의 배열 A와 배열 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.

N, K 그리고 배열 A와 배열 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

 

 

 

 

입력 조건

 

• 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1<=N<=100,000 , 0<=K<=N)
• 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
• 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 자은 자연수입니다.

 

 

 

 

출력 조건

 

• 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

 

 

 

 

풀이 과정 & 분석

 

이 문제도 매우 쉽다. A와 B를 정렬하여 A의 가장 작은 원소가 B의 가장 큰 원소보다 작다면 swap하면 된다. Collections.reverse(b) 해서 뒤집었으면 코드가 더 깔끔했을 듯하다.

 

입력 조건을 보면 N이 100,000 이하이므로 시간 복잡도가 O(NlogN) 이하인 정렬을 사용하여야 한다. 그래서 나는 간편하게 자바에 내장된 정렬 함수 Collections.sort()를 사용하였다.

 

 

 

 

Java 코드

 

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


public class Main {

    public static List<Integer> a = new ArrayList<>();
    public static List<Integer> b = new ArrayList<>();

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int result = 0;

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

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

        Collections.sort(a);
        Collections.sort(b);

        for (int i = 0; i < k; i++) {
            if (a.get(i) < b.get(n - 1 - i)) {
                int temp = a.get(i);
                a.set(i, b.get(n - 1 - i));
                b.set(n - 1 - i, temp);
            }
        }

        for (int i = 0; i < n; i++) {
            result += a.get(i);
        }

        bw.write(String.valueOf(result));

        br.close();
        bw.close();
    }
}