1599번: 민식어

문제 출처 : https://www.acmicpc.net/problem/1599

 

언어 : Kotlin

 

문제 설명 :

무엇인가를 창조하는 것은 어렵다. 오민식은 지금까지 어려운 다른나라의 언어를 쓰면서 백성들이 고통에 받는 것을 슬퍼하고 새로운 언어를 만들고자 했다. 그는 창조의 고통에 시달리던 중에 결국 오영식에게 자신의 못다 이룬 꿈을 꼭 이루어달라면서 오영식에게 창조의 임무를 넘겼다.

오영식은 자신의 형이 창조에 고통에 시달리는 모습을 보고 마음이 아파서 자신은 창조를 하지 않기로 했다. 영식이는 표절을 하기로 했는데 세계적인 추세에 맞게 영어를 표절하기로 했다.

영식이는 자신의 형의 이름을 따서 민식어라고 이름붙였다.

민식어에는 알파벳이 20개가 있다.

영어는 a b c d e f g h i j k l m n o p q r s t u v w x y z의 순서이지만, 민식어는 a b k d e g h i l m n ng o p r s t u w y의 순서이다.

민식어는 영어의 순서를 따르기는 하지만, 약간 변형시켜서 따른다. 그리고 ng는 n과 o사이에 오는 하나의 알파벳이다. ng는 무조건 이 알파벳으로 생각한다.

영식이는 사람들이 쉽게 민식어를 배울 수 있도록 민식어 사전을 만들려고 한다. 따라서 몇 개의 단어를 정렬하고자 한다. 민식어 단어가 주어졌을 때, 그것을 민식어의 순서대로 정렬하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 민식어 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 한 줄에 하나씩 단어가 입력으로 들어온다. 단어의 길이는 최대 50자이다. 민식어에 없는 알파벳이 입력으로 주어지는 경우는 없다. 모든 단어는 중복되지 않는다.

 

출력 :

첫째 줄부터 차례대로 정렬한 결과를 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
4 abakada alpabet tagalog ako	abakada ako alpabet tagalog
6 ang ano anim alak alam alab	alab alak alam anim ano ang
6 siya niya kaniya ikaw ito iyon	kaniya ikaw ito iyon niya siya
5 kaba baka naba ngipin nipin	baka kaba naba nipin ngipin
7 knilngiggnngginggn ingkigningg kingkong dingdong dindong dingdont ingkblot	kingkong knilngiggnngginggn dindong dingdont dingdong ingkblot ingkigningg
4 silangang baka bada silang	baka bada silang silangang

 

풀이 : 

customSort를 하는 문제.

Comparator를 사용해 각 단어의 문자를 비교, 차이가 있는 첫 문자에서 정렬 순서를 결정한다.

이때, 이 정렬 순서는 문제에서 주어진 pattern을 사용하는데 orderMap으로 콜렉션 함수인 .associate {}를 사용해 Key와 Value로 묶은 Map을 사용한다.

 

하지만 char가 아닌 string으로 분류되는 "ng"가 두 글자이기 때문에 특별히 처리해야 한다.

문자를 비교할때 "ng" 패턴이 발견된다면 해당 패턴으로 비교하고 idx를 그만큼 건너 뛴다. 그게 아니라면 한 글자 비교를 시행한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val pattern = listOf("a", "b", "k", "d", "e", "g", "h", "i", "l", "m", "n", "ng", "o", "p", "r", "s", "t", "u", "w", "y")
    val dic = List(readLine().toInt()) { readLine() }

    bw.write(customSort(dic, pattern).joinToString("\n"))
    bw.flush()
    bw.close()
}

fun customSort(dic: List<String>, order: List<String>): List<String> {
    val orderMap = order.withIndex().associate { it.value to it.index }

    return dic.sortedWith(Comparator { o1, o2 ->
        var i = 0
        var j = 0

        while (i < o1.length && j < o2.length) {
            val sub1 = if (i < o1.length - 1 && o1.substring(i, i + 2) == "ng") "ng" else o1[i].toString()
            val sub2 = if (j < o2.length - 1 && o2.substring(j, j + 2) == "ng") "ng" else o2[j].toString()

            val order1 = orderMap[sub1] ?: Int.MAX_VALUE
            val order2 = orderMap[sub2] ?: Int.MAX_VALUE

            if (order1 != order2) return@Comparator  order1 - order2

            i += if (sub1 == "ng") 2 else 1
            j += if (sub2 == "ng") 2 else 1
        }

        o1.length - o2.length
    })
}