백준 4358 생태학 Kotlin (map,트라이)

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

4358번: 생태학

문제

생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다.

입력

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다.

출력

주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다.

힌트

입력에는 영문 대소문자와 공백문자, 그리고 숫자, 특수문자만 포함될 수 있다.

알고리즘 분류

• 자료 구조
• 문자열
• 해시를 사용한 집합과 맵
• 트리를 사용한 집합과 맵

풀이

그냥 Hash를 쓰거나 트라이 자료구조를 사용해서 풀 수 있는 문제이다.

트라이를 연습하기 좋은 문제이고, 본인은 TreeMap을 이용한 풀이, 트라이를 이용한 풀이 두 가지로 풀었다.

만약 이 문제가 코테에 나온다면 빠르게 TreeMap으로 풀고 넘어가자. 입력 값이 굳이 트라이를 쓸 필요가 없다.

 

1.TreeMap

우선 트라이를 쓰든 해쉬만 쓰든 정렬은 해야 한다.

따라서 HashMap이 아닌 TreeMap을 써주자.

정말 별 거 없다.

그냥 트리맵 하나 만들어 놓고 나무의 개수를 센다.

트리맵은 자동 정렬되니 이후 트리맵을 순회하면서 출력하면 끝

 

2.Trie

코틀린으로 짠 트라이 레퍼런스는 거의 못 본 것 같다.

다행히 예전 문제에서 짜 놓은 게 있어서 보고 짰다.

2021.08.03 - [알고리즘 문제 풀이/백준] - 백준 5052 전화번호 목록 c++ (트라이)

몇 개월만에 트라이인가..

본인은 트라이에 대한 이해도가 높진 않아서 설명을 적진 않겠다.

아쉽지만 트라이 자료구조에 대한 설명을 다른 곳에서 공부한 뒤, 코드만 참고하길 바란다.

 

풀이는 다음과 같다.

1.1 트라이에 나무 종을 모두 저장한다.

1.2 트라이에 저장하면서 트라이에 cnt값을 두어 개수를 센다

2. TreeSet을 하나 만들어 여기에 추후 탐색할 나무 종들을 중복 없이 오름차순 정렬된 상태로 저장한다.

3. TreeSet을 순회하며 트라이에 있는 나무 종의 카운트를 백분율 소수 넷째 자리까지 출력한다.

 

참고로 String.format(".4f", 0.12345)는 소수점 다섯째 자리에서 반올림해준다!

코드1(TreeMap)

//O(logN*logN) - TreeMap
//get에 logN
//insert에 logN

import java.util.*

val br = System.`in`.bufferedReader()
fun main() = with(System.out.bufferedWriter()){

     val map = TreeMap<String, Double>()
     var size=0
     while(true){
         val input = br.readLine() ?: break
         map[input] = map.getOrDefault(input,0.0)+1
         size++
     }

     map.forEach{
         write("${it.key} ${String.format("%.4f",it.value/size*100)}\n")
     }

     close()
}

코드2(Trie+TreeSet)

//2. Trie + TreeSet

//길이 : L
//문자열의 수 : M
//O(M*L) - Trie
//TreeSet 삽입 O(logN)
//문제 시간 복잡도 O(M*L)
import java.util.*

val br = System.`in`.bufferedReader()

class Trie(var cnt: Int, val node: MutableMap<Char, Trie>){

    fun insert(word: String){
        var children: Trie = this
        for(ch in word){
            //노드에 ch엣지가 연결되어 있으면 이동
            if(children.node.containsKey(ch)){
                children = children.node[ch]!!
            }
            //엣지가 연결되어 있지 않으면 새로 생성 후 연결
            else{
                children.node[ch] = Trie(0, mutableMapOf())
                children = children.node[ch]!!
            }
        }
        //단어의 끝에 카운팅
        children.cnt++
    }

    fun getCount(word: String): Int{
        var children = this
        //무조건 있을겨
        for(ch in word){
            children = children.node[ch]!!
        }
        return children.cnt
    }

}

fun main() = with(System.out.bufferedWriter()){

    val root = Trie(0, mutableMapOf())
    val treeSet = TreeSet<String>()
    var size=0

    while(true){
        val input = br.readLine() ?: break
        root.insert(input)
        treeSet.add(input)
        size++
    }

    for(set in treeSet) {
        write("$set ${String.format("%.4f", root.getCount(set).toDouble()/size*100)}\n")
    }

    close()
}