정렬 알고리즘 활용 문제 풀이

BOJ 10989 수 정렬하기 3

Arrays.sort 로도 풀리지만 counting sort를 사용하는 방법도 있다.

counting sort의 시간복잡도는 O(n + k)으로 매우 빠른 정렬 방식이지만 수의 범위만큼 메모리를 차지하기 때문에 범위가 제한되어 있고 1000만이하일 때 사용하는 것이 좋다

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val count = IntArray(10001)

    repeat(n) {
        count[readLine().toInt()]++
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    for (i in 1..10000) {
        if (count[i] != 0) {
            repeat(count[i]) {
                bw.write("$i\n")
            }
        }
    }
    bw.close()
}

BOJ 10814 나이순 정렬

kotlin

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var n = readLine().toInt()
    val userList = mutableListOf<User>()

    var st: StringTokenizer
    while (n-- != 0) {
        st = StringTokenizer(readLine())
        userList.add(User(st.nextToken().toInt(), st.nextToken()))
    }

    userList.sortBy { it.age }
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    repeat(userList.size) {
        bw.write("${userList[it].age} ${userList[it].name}\n")
    }
    bw.close()
}

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());
        List<User> userList = new ArrayList<User>(n);

        StringTokenizer st;
        while (n-- != 0) {
            st = new StringTokenizer(br.readLine());
            userList.add(new User(Integer.parseInt(st.nextToken()), st.nextToken()));
        }

        Collections.sort(userList, (o1, o2) -> o1.age - o2.age);

        for (User u: userList) {
            bw.write(u.age + " " + u.name + "\n");
        }
        bw.close();
    }

    public static class User {
        int age;
        String name;

        public User(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }
}

BOJ 11650. 좌표 정렬하기

kotlin

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var n = readLine().toInt()
    var st: StringTokenizer
    val dotList = mutableListOf<Dot>()
    while (n-- != 0) {
        st = StringTokenizer(readLine())
        dotList.add(Dot(st.nextToken().toInt(), st.nextToken().toInt()))
    }
    dotList.sortWith{ o1, o2 -> if (o1.x == o2.x) o1.y - o2.y else o1.x - o2.x }
    repeat(dotList.size) {
        bw.write("${dotList[it].x} ${dotList[it].y}\n")
    }
    bw.close()
}

private data class Dot(val x: Int, val y: Int)

java

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        List<Dot> dotList = new ArrayList<>(n);
        StringTokenizer st;
        while (n-- != 0) {
            st = new StringTokenizer(br.readLine());
            dotList.add(new Dot(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        dotList.sort((o1, o2) -> {
            if (o1.x == o2.x) return o1.y - o2.y;
            else return o1.x - o2.x;
        });

        for (Dot d: dotList) {
            bw.write(d.x + " " + d.y + "\n");
        }
        bw.close();
    }

    public static class Dot {
        int x;
        int y;

        Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

BOJ 11652. 카드

11652번: 카드

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val arr = LongArray(n)

    repeat(n) {
        arr[it] = readLine().toLong()
    }

    arr.sort()

    var maxVar = arr[0]
    var maxCnt = 1
    var cnt = 1
    for (i in 1 until n) {
        if (arr[i] == arr[i-1]) cnt++
        else {
            if (maxCnt < cnt) {
                maxCnt = cnt
                maxVar = arr[i-1]
            }
            cnt = 1
        }
    }

	// 제일 마지막 수
    if (cnt > maxCnt) maxVar = arr[n-1]
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write("$maxVar")
    bw.close()
}

 

BOJ 1431. 시리얼 번호

시리얼 번호 A가 B의 앞에 오는 경우는 다음과 같다.
1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다
2. 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다 (숫자만 더한다)
3. 1,2 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다

기타의 개수 N개(N <= 50), 시리얼 번호의 길이 최대 50이고 A-Z, 0-9로 이루어져 있으며 중복되지 않는다.

1. 길이로 정렬

2. 숫자합으로 정렬

3. 사전순으로 정렬

 

kotlin

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var n = readLine().toInt()
    val list = mutableListOf<String>()

    while (n-- != 0) {
        list.add(readLine())
    }

    // 정렬 조건 명시
    val compareLength = compareBy<String> { it.length }
    val compareSum = compareLength.thenBy { s ->
        var sum = 0
        s.forEach { if (it in '0'..'9')  sum += it.digitToInt() }
        sum
    }
    val compareAlphabet = compareSum.thenBy { it }
    list.sortWith(compareAlphabet)

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    repeat(list.size) {
        bw.write("${list[it]}\n")
    }
    bw.close()
}

java

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());
        String[] arr = new String[n];

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

        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                if (s1.length() == s2.length()) {
                    int sum1 = sum(s1);
                    int sum2 = sum(s2);
                    if (sum1 == sum2) return s1.compareTo(s2);
                    else return sum1 - sum2;
                } else {
                    return s1.length() - s2.length();
                }
            }

            private int sum(String s) {
                int sum = 0;
                for(int i = 0; i < s.length(); i++) {
                    int num = s.charAt(i) - '0';
                    if (num >= 0 && num <= 9) sum += num;
                }
                return sum;
            }
        });

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (String s : arr) {
            bw.write(s + "\n");
        }
        bw.flush();
        bw.close();
    }
}

자바로 짜기 싫다 ㅎㅎ

BOJ 5648. 역원소 정렬

원소를 뒤집은 후 오름차순으로 정렬하기

 

kotlin

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

fun main() {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val arr = arrayOfNulls<Long>(n)
    var idx = 0

    while (idx < n) {
        arr[idx++] = sc.next().reversed().toLong()
    }

    arr.sort()
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    repeat(arr.size) {
        bw.write("${arr[it]}\n")
    }
    bw.close()
}

 

BOJ 1181. 단어 정렬

소문자로 이루어진 N개의 단어 정리 (1 ≤ N ≤ 20,000)
1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로
중복된 단어는 하나만 남기고 제거해야 한다

kotlin

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var n = readLine().toInt()
    val list = mutableListOf<String>()
    while (n-- != 0) {
        list.add(readLine())
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))

    list.distinct().sortedWith { s1, s2 ->
        if (s1.length == s2.length) {
            s1.compareTo(s2)
        } else s1.length - s2.length
    }.forEach {
        bw.write("${it}\n")
    }

    bw.close()
}

java

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

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

        while (n-- != 0) {
            list.add(br.readLine());
        }

        // 중복제거
        Set<String> set = new HashSet<>(list);
        List<String> nList = new ArrayList<>(set);
        // 정렬
        nList.sort((s1, s2) -> {
            if (s1.length() == s2.length()) return s1.compareTo(s2);
            else return s1.length() - s2.length();
        });

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(String s: nList) {
            bw.write(s + "\n");
        }
        bw.close();
    }
}

 

BOJ 2910. 빈도 정렬

C (1 ≤ C ≤ 1,000,000,000) 보다 작거나 같은 수로 이루어진
n개(1 ≤ N ≤ 1,000) 의 수열을 빈도순대로 정렬하라.

- x가 y보다 많이 등장할 경우 x가 y보다 앞에 있어야 한다.
- 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

빈도수 체크라서 couting sort도 고려해봤으나 c의 범위가 매우 커서 제외하고 map으로 풀었다

1. map을 사용해서 나오는 숫자와 빈도수를 체크한다

2. 빈도수로 내림차순 정렬 후 출력한다

 

kotlin

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val c = st.nextToken().toInt()

    val map = mutableMapOf<Int, Int>()
    st = StringTokenizer(readLine())
    repeat(n) {
        val num = st.nextToken().toInt()
        if (map.containsKey(num)) map.replace(num, map[num]!!.plus(1))
        else map[num] = 1
    }

    val sorted = map.toList().sortedByDescending { it.second }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    repeat(map.keys.size) { i ->
        repeat(sorted[i].second) {
            bw.write("${sorted[i].first} ")
        }
    }
    bw.close()

}

 

BOJ 7795. 먹을 것인가 먹힐 것인가

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇개나 있는지 구하라
A는 자기보다 크기가 작은 먹이만 먹을 수 있다.
A,B의 수 (1 ≤ N, M ≤ 20,000) 

1. 수열 a와 b를 오름차순으로 정렬

a[1, 1, 3, 7, 8], b[1, 3, 6]

 

2. b의 원소보다 큰 a의 원소 수를 구한다

예. b가 1일 때 a에서 b보다 큰 수를 구한다

a에서 1보다 큰 최초로 등장하는 원소는 3이고 인덱스값은 2이다. 

정렬된 상태이기 때문에 a에서 더 탐색을 진행하지 않아도 그 뒤에 값은 1보다 크다는 걸 알수있다.

따라서 n-idx를 하면 1보다 큰 a의 원소 수를 구할 수 있다.

다음 탐색 때 b의 원소는 현재보다 클 것이기 때문에 a에서 idx보다 작은 부분은 비교할 필요가 없이 작다는 것을 알수있다.

 

kotlin

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var t = readLine().toInt()
    var n: Int
    var m: Int
    var st: StringTokenizer

    while (t-- != 0) {
        // input
        st = StringTokenizer(readLine())
        n = st.nextToken().toInt()
        m = st.nextToken().toInt()

        val a = IntArray(n)
        st = StringTokenizer(readLine())
        repeat(n) {
            a[it] = st.nextToken().toInt()
        }
        st = StringTokenizer(readLine())

        val b = IntArray(m)
        repeat(m) {
            b[it] = st.nextToken().toInt()
        }
        // sort
        a.sort()
        b.sort()

        // a가 b보다 큰 경우 구하기
        var idx = 0
        var cnt = 0
        for (i in 0 until m) {
            for (j in idx until n) {
                if (b[i] < a[j]) {
                    idx = j
                    cnt += n-idx
                    break
                }
            }
        }
        bw.write("$cnt\n")
    }
    bw.close()
}

 

BOJ 11656. 접미사 배열

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.
접미사를 사전순으로 정렬 후 출력하는 프로그램을 작성하시오.

문자열 잘라서 리스트에 저장 후 정렬

 

kotlin

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val s = readLine()
    val list = mutableListOf<String>()

    repeat(s.length) {
        list.add(s.substring(it until s.length))
    }
    list.sort()
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    repeat(list.size) {
        bw.write("${list[it]}\n")
    }
    bw.close()
}