백준 26265번
https://www.acmicpc.net/problem/26265
문제
생각하기
-
문자열을 문제에서 제시한 조건대로 정렬만 하면 되는 문제이다.
-
자바의 경우 Comparator를 재정의 할 필요가 있다.
동작
Collections.sort(mentoList, kotlin.Comparator { o1, o2 ->
return@Comparator if (o1.mento > o2.mento) {
1
} else if (o1.mento < o2.mento) {
-1
} else {
if (o1.menti > o2.menti) {
-1
} else if (o1.menti < o2.menti) {
1
} else {
0
}
}
})
mentoList에 저장하는 부분은 그리 특별하지 않고
원래 Collections 정렬을 하던 sort를 재정의 해야하는 코드가 필요했다.
위 코드를 통해서 문제에서 제시한 조건으로 정렬하게 된다.
특정 조건에 따라 반환값을 1, 0, -1로 구분하여 정렬하게 된다
if (o1.mento > o2.mento) {
1
}의 경우 1을 return 하는데 o1.mento가 앞에 오고 o2.mento가 뒤에 온다 즉 1은 일반 오름차순 정렬이고
조건에 따라 역순 즉, o1.mento가 뒤로 가야할 때는 -1을 return하면 역순으로 정렬 할 수 있게된다.
0은 그냥 같은 값이므로 특별히 할 조건이 없다.
번외
처음에 이 문제가 정렬 문제임을 파악하고 PriorityQueue는를 사용하려고 했는데,
분명히 정렬조건을 제대로 구현했음에도 불구하고 삽입을 모두 한 후 출력하면 내가 원하는 결과가 나오지 않았다.
그래서 어쩔수없이 그냥 List에 모두 삽입한 후에 정렬을 하는 방법을 선택하여 정답을 찾게 되었다.
정답을 맞추고 난 후에도 왜 PriorityQueue는 내가 원하는 방법대로 출력되지 않았는지를 고민했는데
그 이유는 PriorityQueue 자체가 Heap을 기초로 두고있기 때문에 Heap의 자료구조를 이해하는게 중요했다.
나는 그걸 몰랐음
PriorityQueue에서는 내부 원소가 안에서 정렬된 상태가 아니라는 것을 알게됬음
힙 구조상 내부에서 오로지 부모 > 자식 성질만 유지되기 때문에
8
6 7
도 올바른 힙이고
8
7 6
도 올바른 힙 구조에요위 같은 설명을 들을 수 있었다
그렇기 때문에 내가 원하는 결과를 얻을 수 없었던 것.
여기서 내가 출력을 했을때는 원하는 결과를 얻을 수 없었지만,
다른 방법으로 PriorityQueue를 하나씩 빼면서 즉, poll() 하면서 나오는 값을 출력해보면 그때서야 원하는 정렬된 값이 제대로 나오는 것을 알 수 있었다.
결론 : Heap의 자료구조를 더 공부할 필요성이 있다는 것을 느낌
아래는 Pque를 사용했을 때 결과
확실히 조금 빠르기한듯
코드
Kotlin
LinkedList + Sort()
import java.util.*
import java.io.*
import java.lang.StringBuilder
private var N = 0
private var mentoList = LinkedList<Mento>()
private data class Mento(var mento: String = "", var menti: String = "") // End of Mento class
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.`out`))
val sb = StringBuilder()
N = br.readLine().toInt()
for (i in 0 until N) {
val st = StringTokenizer(br.readLine())
mentoList.offer(Mento(st.nextToken(), st.nextToken()))
}
Collections.sort(mentoList, kotlin.Comparator { o1, o2 ->
return@Comparator if (o1.mento > o2.mento) {
1
} else if (o1.mento < o2.mento) {
-1
} else {
if (o1.menti > o2.menti) {
-1
} else if (o1.menti < o2.menti) {
1
} else {
0
}
}
})
mentoList.forEach {
sb.append(it.mento).append(' ').append(it.menti).append('\n')
}
bw.write(sb.toString())
bw.close()
} // End of main
PriorityQueue를 사용
import java.util.*
import java.io.*
import java.lang.StringBuilder
private var mentoQue = PriorityQueue { o1: Mento, o2: Mento ->
return@PriorityQueue if (o1.mento > o2.mento) {
1
} else if (o1.mento < o2.mento) {
-1
} else {
if (o1.menti > o2.menti) {
-1
} else if (o1.menti < o2.menti) {
1
} else {
0
}
}
}
private var N = 0
private var mentoList = LinkedList<Mento>()
private data class Mento(var mento: String = "", var menti: String = "") // End of Mento class
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.`out`))
val sb = StringBuilder()
N = br.readLine().toInt()
//원래 처음 풀려고했던 방식인데 틀린 코드
for (i in 0 until N) {
val st = StringTokenizer(br.readLine())
mentoQue.offer(Mento(st.nextToken(), st.nextToken()))
}
while (!mentoQue.isEmpty()) {
val temp = mentoQue.poll()
sb.append(temp.mento).append(' ').append(temp.menti).append('\n')
}
bw.write(sb.toString())
bw.close()
} // End of main
