문제: 프로그래머스: 달리기 경주
문제
아래 2개
players: 현재 1등부터 마지막까지 등수 순으로 선수들의 이름이 담겨 있는 문자열 배열- 중복된 선수 이름은 존재하지 않음
- 배열 길이 범위: [5, 50000]
callings: 해설진이 부른 선수들 이름이 담겨 있는 문자열 배열- 선수가 자기 바로 앞의 선수를 추월할 때 해당 선수 이름을 부르게 됨
players에 존재하는 선수들 이름만 존재하며, 여러 번 불릴 수 있음- 1등인 선수의 이름은 불리지 않음
- 배열 길이 범위: [2, 1000000] -가 입력으로 주어졌을 경우,
callings에 있는 모든 이름들이 불려지고 난 후 선수들 상황을 1등부터 마지막까지 배열로 반환하는 문제.
접근
O(N^2)으로는 무리
’해설진이 선수 이름을 불렀을 때 선수가 자기 바로 앞의 선수를 추월한다’는 해당 선수의 순위가 한 단계 올라갔다는 걸 의미하고, 이건 바로 앞에 있던 선수의 순위가 한 단계 내려간다는 걸 의미하며, 이걸 합치면 해당 선수와 바로 앞의 선수의 순위가 바뀐다가 된다.
단순히 players의 복사본을 가지고 와서, 불린 선수를 이 배열에서 (앞에서부터) 찾은 다음 바로 앞(이전 인덱스)의 선수와 순서를 바꾸는 것도 해결이 가능하지만…
50000명의 선수가 달리기를 하는데 해설진이 1000000번 동안 매번 맨 마지막에 있는 선수들만 불렀다면?
이런 상황에선
for i = 1 to callings.length
for j = 1 to players.length
if players[j] == callings[i] // comp
swap(players[j - 1], players[j])-와 같은 시간복잡도 O(N^2)의 코드로는 comp 부분이 500억번(!)이나 불리게 될 것이다. 보통 사람들이 이야기하는 “컴퓨터는 1초에 1억번 연산을 거쳐요”라는 말을 참고로 하면, 이런 극한의 상황에선 comp를 돌리는 데만 500초(8분 20초)나 걸린다는 이야기다. 더 짧은 시간복잡도를 가지는 코드를 찾아봐야 한다.
map
C++ 기준이지만, key/value 삽입이나 key에 대응하는 value 접근에 일반적으로 O(log N)의 시간복잡도를 가진다고 한다(추가 / 접근). O(N^2)에서 O(log N)으로 바뀐다는 건, 100만 개의 원소를 훑어볼 때 1조(10^12)번을 훑어봐야 했을 수 있던 걸 20(log(100000, 2))번(혹은 6(log(1000000, 10))번)으로 줄일 수 있는 아주 시간적으로 이득을 많이 볼 수 있는 상황이다.
이런 map을 이용해서
- 현재 시점의 (선수 이름, 순위) 조합을
map에 삽입한다. - 현재 시점의 (순위별) 선수 이름이 담긴
players를 다른 곳에 복사한다. callings에서 선수 이름을 부를 때 마다 1의 그것과 2의 그것에 순위 변동 사항을 갱신시킨다.
-의 과정을 거치면 풀 수 있을 것 같았다. 이걸 조금 코드에 가깝게 표현하면
playersCopied = players.copy() // index: 순위, value: 선수 이름
playersRank = Map<String, Int> // key: 선수 이름, value: 순위
for i = 1 to playersCopied.length
playersRank.put(playersCopied[i], i)
for i = 1 to callings.length
calledRank = playersRank.get(callings[i]) // 불린 선수의 현재 순위
precededPlayer = playersCopied[calledRank - 1] // 불린 선수의 현재 순위 바로 위에 있는 선수
swap(playersRank[callings[i]], playersRank[precededPlayer]) // 두 선수의 순위 교체(순위 변경)
swap(playersCopied[calledRank], playersCopied[calledRank - 1]]) // 두 순위에 있는 선수 교체(이름 변경)
return playersCopied // 순위 변동을 모두 적용한 후의 playersCopied 반환가 되고, 이걸 Kotlin 코드로 옮겨적으면
class Solution {
fun solution(players: Array<String>, callings: Array<String>): Array<String> {
var nameByRank = players.copyOf()
var rankByName: MutableMap<String, Int> = mutableMapOf()
var targetRank: Int
var precededOne: String
for (i in nameByRank.indices) rankByName.put(nameByRank[i], i)
for (calling in callings) {
targetRank = rankByName[calling]!!
precededOne = nameByRank[targetRank - 1]
rankByName[precededOne] = rankByName[calling]!!.also { rankByName[calling] = rankByName[precededOne]!! }
nameByRank[targetRank] = nameByRank[targetRank - 1].also { nameByRank[targetRank - 1] = nameByRank[targetRank] }
}
return nameByRank
}
}가 될 것이다(의사코드에 있던 playersCopied는 nameByRank, playersRank는 RankByName으로 표현하였다 순위랑 선수 이름 중 누가 키/인덱스로 오는지만 차이가 있어서 그렇게 지었다).
Kotlin에 있는 MutableMap의 경우 해당 key에 대응하는 value가 존재하지 않을 수 있기 때문에 저렇게 non-null assersion operator(!!)를 써 줘야 한다.