1. 개요
오늘 문제는 난이도 측면에서 어렵다고 느끼진 않았지만, 코틀린이라는 언어가 내게 새롭다보니 문법을 잘 몰라서 좀 무식하게 풀었다.
2. 코드
class Solution {
fun solution(weights: IntArray, head2head: Array<String>): IntArray {
// 1) 필요한 요소들 정리
val len = head2head.size
var results = Array<IntArray>(len, {IntArray(4)})
var arr = IntArray(len)
var winlist = DoubleArray(len)
// 2) 비교하면서 배열 위치 바꿔주기
for (i in 0 until len) {
var check = head2head[i]
var curWeight = weights[i]
var tot = 0
var heavy = 0
var cnt = len
for (j in 0 until len) {
var tmp = check.get(j)
if (tmp == 'W') {
tot += 1
if (weights[j] > curWeight) {
heavy += 1
}
}
else if (tmp == 'N') {
cnt -= 1
}
}
var winrate = 0.0
if (cnt == 0) {
winrate = 0.0
} else {
winrate = 100*tot/cnt.toDouble()
}
winlist[i] = winrate
results[i][1] = heavy
results[i][2] = curWeight
results[i][3] = i
}
// 3) 전체 요소들 사용해서 정렬
for (i in 0 until len) {
for (j in 0 until len-1-i) {
if (winlist[j] < winlist[j+1]) {
var tmp = results[j]
results[j] = results[j+1]
results[j+1] = tmp
var tmp1 = winlist[j]
winlist[j] = winlist[j+1]
winlist[j+1] = tmp1
} else if (winlist[j] == winlist[j+1]) {
if (results[j][1] < results[j+1][1]) {
var tmp = results[j]
results[j] = results[j+1]
results[j+1] = tmp
} else if (results[j][1] == results[j+1][1]) {
if (results[j][2] < results[j+1][2]) {
var tmp = results[j]
results[j] = results[j+1]
results[j+1] = tmp
} else if (results[j][2] == results[j+1][2]) {
if (results[j][3] > results[j+1][3]) {
var tmp = results[j]
results[j] = results[j+1]
results[j+1] = tmp
}
}
}
}
}
}
for (i in 0 until len) {
arr[i] = results[i][3] + 1
}
return arr
}
}3. 해설
말 그대로 정말 무식하게 풀었다.
1) 먼저 결과 배열과 비교할 값을 입력받을 배열을 생성하였다.
2) 비교하면서 위치를 바꿔주었다.
이때 불필요한 요소들이 있는 건, 너무 조급하게 풀어서 그렇다.
또한 하나의 IntArray가 아니라 객체를 만들거나 해도 되는데, 문제를 풀 때에는 그 부분을 생각하질 못했다.
3) 정말 긴 비교 및 정렬 코드다. 정말 다시 보니까 새삼스럽게 더럽다.
하나의 메서드를 하거나 Comparator를 사용해도 되는데, 반성해야겠다.
4. 참조한 코드
"최철훈" 님이 사용한 코드를 참조하였다. 지금 수준에서는 그나마 이해할 수 있으면서 내가 쓴 코드보다 깔끔하기에 참조했다.
class Solution {
fun solution(weights: IntArray, head2head: Array<String>): IntArray {
val len = head2head.size
val list: MutableList<Boxer> = ArrayList<Boxer>()
for (i in 0 until len) {
var check = head2head[i]
var curWeight = weights[i]
var tot = 0
var heavy = 0
var cnt = len
for (j in 0 until len) {
var tmp = check.get(j)
if (tmp == 'W') {
tot += 1
if (weights[j] > curWeight) {
heavy += 1
}
}
else if (tmp == 'N') {
cnt -= 1
}
}
var winrate = 0.0
if (cnt == 0) {
winrate = 0.0
} else {
winrate = 100*tot/cnt.toDouble()
}
list.add(Boxer(i+1, curWeight, heavy, winrate))
}
// 전체 요소들 사용해서 정렬
list.sortWith(Comparator { o1: Boxer, o2: Boxer ->
if (o1.rate < o2.rate) 1
else if (o1.rate == o2.rate) {
if (o1.bigger < o2.bigger) 1
else if (o1.bigger == o2.bigger) {
if (o1.weight < o2.weight) 1
else if (o1.weight == o2.weight)
o1.number - o2.number
else -1
} else -1
} else -1
})
return list.map { it.number }.toIntArray()
}
internal class Boxer(var number: Int, var weight: Int, var bigger: Int, var rate: Double)}``` ```
5. 시간복잡도
weights의 최대 길이는 1000이다.
먼저 weights의 길이(head2head의 길이와 동일)만큼 반복문을 사용하고, 또 그 안에 weights의 길이만큼 반복문을 사용하기에 이 부분의 시간복잡도는 O(1000^2)가 된다.
다음으로 정렬하는 부분에서는 버블 정렬을 사용했으며, 따라서 시간복잡도는 O(n^2) = O(1000^2)가 된다.
시간복잡도는 O(1000^2) + O(1000^2)가 되며, 최종적인 시간복잡도는 O(1,000,000)가 된다.
파이썬은 천만 단위의 계산에 대략 1초가 걸린다.
코틀린은 그보단 빠르기에, 이정도 시간복잡도면 충분히 괜찮다고 생각한다.
6. 공간복잡도
거품 정렬을 사용했으므로 총 O(n) = O(1000)입니다.
주어진 배열 안에서 교환을 통해 정렬이 수행되기 때문입니다.
7. 버블 정렬을 사용한 이유
버블 정렬을 사용한 이유는 우선 구현이 간단했기 때문이며, 또한 여러 개의 값을 순서대로 비교하면서 정렬해야 하기에 안정 정렬이 필요했습니다. 따라서 버블 정렬을 사용했습니다.
물론 시간복잡도가 최악, 최선, 평균 모두 O(n^2)이기 때문에 매우 비효율적이고, 원소를 교환하는 연산이 많이 일어나게 됩니다.
