백준 1181) 단어 정렬

www.acmicpc.net/problem/1181

1181번: 단어 정렬

 

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

 

 

 

---

 

 

문제에 주어진 조건 중에서 길이가 짦고, 길이가 같으면 사전 순을 적절하게 구현하려면,

sortWith 와 Comparator 를 사용하면 된다.

 

 

출처 : kotlinlang.org

sortWith 함수는 특정 조건에 부합하도록 Comparator를 구성하면, 원하는 정렬된 값을 얻을 수 있다.

 

 

 

 

문제에 주어진 조건에 따라 만든 코드는 다음과 같다.

 

sortWith(Comparator { o1, o2 ->
            if (o1.length == o2.length) {
                o1.compareTo(o2)
            } else {
                o1.length - o2.length
            }
   	})

 

o1과 o2의 자료형은 Collection 에서 제네릭으로 선언한 자료형과 같다. (여기서는 String)

 

Comparator는 다음과 같은 규칙을 가지고 있다.

• return 값이 음수라면,   o1 < o2 이고,
• return 값이 양수라면,   o1 > o2 이고,
• return 값이 0이라면,    o1==o2 이다.

하지만 문제에서 길이가 같으면 사전 순으로 정리하는 조건이 있으므로,

compareTo 함수를 이용해서 같은 길이의 문자열을 다시 비교해준다.

이 함수 또한 Comparator와 같은 규칙을 가지고 있다.

 

 

 

 

전체 코드는 다음과 같다.

 

import java.io.*
fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val set = hashSetOf<String>()
    //겹치지 않도록 hashSet 이용
    val n = readLine().toInt()

    for(i in 0 until n) {
        set.add(readLine())
    }

    set.toMutableList().apply {
        //hashSet은 sortedWith 밖에 호출되지 않기 때문에,
        //sortWith가 가능한 mutableList로 변경.
        sortWith(Comparator { o1, o2 ->
            if (o1.length == o2.length) {
                o1.compareTo(o2)
            } else {
                o1.length - o2.length
            }
        })
        this.forEach {
            bw.write("$it\n")
        }
    }

    bw.flush()
    bw.close()
}