[BOJ]1181 단어정렬 (kotlin)

1181번: 단어 정렬

이번에 푼 문제는 단어를 두가지 조건에 따라 정렬하는것이었다.

조건은 아래와같다.

1. 단어 길이 순 오름차순 정렬
2. 길이가같다면 알파벳 순으로 정렬
3. 중복되는 단어는 하나로 통일

TRY1. PQ

1번 조건을 보고 자료구조시간에 배운 priorityQueue가 생각났다.

구글링 결과 코틀린에서 pq를 사용하기 위해서는

import java.util.*

위와 같이 사전에 import가 필요하다.

pq를 사용해 코드를 짜보니 조건2가 걸렸다. pair을 사용해 첫번째 원소 기준으로 정렬을 하려고했는데 막상해보니 pq는 일반적인 방법으로는 pair을 원소로 넣을 수 없었다.

검색을 했더니 Comparator라는걸 사용해서 어떻게 할수 있다고 나와있어서 적용해보았는데 comparator 공부를 덜 해서 그런지 문법적인 오류와 실행오류가 꽤 많이 나왔다.

그런 상황에서 collection을 정렬하는방법을 보니 더 간단해 보여서 평소에 잘사용하는 mutableList과 정렬함수 sortedBy를 사용해 정렬을 시도해보았다.

TRY2. sortedBy{}

sortedBy를 사용해 정렬을 시도했다.

//대충 이렇게
list.sortedBy{it.length}
list.forEach{
	println(it)
}

왠지 정렬이 되지 않았다. 참고한 블로그에서는 되는것같았는데,, 좀 당황스러웠다.

TRY3. sortedWith{},comparator,thenBy{}

문제를 찾았다. sortedBy로 리턴되는 값이 정렬된 리스트인데 그걸 저장하지 않고 그냥 이전 데이터를 다룬것이 문제였다!

이부분을 찾다가 블로그에서 이 조건들과 상당히 흡사한 코드를 찾았다. comparaotr로 정렬조건을 명시한 후 두번째 조건은 thenBy를 사용해 comparaor를 결합하여 만든다.

이후 sortedWith를 사용해서 정렬을 완료했다.

val lengthComparator=compareBy<String>{it.length}
    val comparator=lengthComparator.thenBy{it}

    val words= mutableSetOf<String>()

    for(i in 0 until num){
        val word=readLine()!!
        words.add(word)
    }

    words.sortedWith(comparator).forEach{
        print("$it\n")
    }

TRY4. mutableSet사용

출력을 해보니 결과가 뭔가 달랐다. 생각해보니 조건3을 까맣게 잊고있었다!

중복을 없애는데는 set이 가장 간편해보여 mutableList→mutableSet으로 자료형을 변경하였다.

여기까지 해서 문제 제출을 했더니 720ms가 나왔다.

---

[Advanced]

1등의 시간을 보니 252ms가 나왔다.

처리시간이 세배정도 차이가 나는 것을 보니 개선의 여지가 다분해 보였다.

일단 상위권 코드들을 모아서 내 코드와 차이점을 분석 해보았다.

• 차이점1 : 입출력 버퍼

    BufferedReader(InputStreamReader(System.`in`))
    BufferedWriter(OutputStreamWriter(System.out))
  

  아래 블로그에 따르면 기존에 썼던 코드는 키보드 입력 즉시 입력을 프로그램으로 보내는것이고 위의 입출력버퍼를 사용하면 키보드 입력을 버퍼에 임시로 모아두었다가 버퍼가 다 차거나 개행문자를 만났을때 한번에 프로그램으로 보낸다.

  그냥 들었을때는 둘이 큰 차이가 없어보이지만 데이터 입출력은 자원이 많이 필요하므로 한번에 보내는것이 더 효율적이라고 한다.

  BufferedReader & BufferedWriter - 빠른 입출력(Kotlin - 코틀린). feat, 자바

• 차이점2 : 정렬방식

  자료구조시간에 정렬 방법을 몇개 배웠었는데 그중 퀵솔트 방식을 쓴 코드들이 종종 보였다. 이부분은 기억이 희미하기도하고 다 못배운 정렬방법도 있어서 나중에 다시 공부해서 따로 포스팅을 하기로한다.