오늘의 TIL!
오늘도 역시나 첫번째주인만큼 알고리즘 문제풀이를 하는 시간을 가졌다.
오늘내가 집중적으로 공부한 부분은 HashMap이다. HashMap에 대해서 자세하게 공부하게된 이유는
'달리기 경주' 라는 프로그래머스 알고리즘문제를 풀다가 나오게 되었다.
먼저 문제와 입출력의 예를 보면
callings배열에서 이름이 불리면 players에 있는 사람이 자신의 앞 사람을 앞질렀다고 생각하고, callings배열을 모두 순회한 후의 결과를 return해주는 문제였다.
나는 처음에 callings에서 "kai"라는 이름이 불리면 players배열안에서 "kai"값의 인덱스를 찾아와 해당인덱스의 값과 해당인덱스-1 의 값을 서로 바꿔주었다. 그 결과
class Solution {
fun solution(players: Array<String>, callings: Array<String>): Array<String> {
var finalList = players.toMutableList()
for(i in 0 until callings.size){
var playerindex = finalList.indexOf(callings[i])
var winPlayer = finalList[playerindex]
var losePlayer = finalList[playerindex-1]
finalList.set(playerindex-1, winPlayer)
finalList.set(playerindex, losePlayer)
}
return finalList.toTypedArray()
}
}원하는 값을 얻을 수 있었다. 하지만 중요한사실이 하나 있었다. 이 문제에는 제한사항이 존재했는데,
players의 길이는 5이상 50,000이하여야한다.
callings의 길이는 2이상 1,000,000이하여야한다.
입출력 예에서처럼 해당 값들이 작다면 전혀 문제가 되지 않지만 만약 players의 길이가 50,000이고 callings의 길이가 1,000,000이라면..? 이 코드는 무수히 많은 반복문을 돌게 될것이고, index를 찾기위해서 무수히 많은 과정을 거치게 될것이다.
제출결과 -> 역시 시간초과가 나오는 문제들이 존재했다.
이 문제에 대해 시간을 줄이기 위해서 HashMap을 이용해보기로 했다.
HashMap은 키를 해시코드로 변환하여 배열의 인덱스를 저장한다. 이는 특정 키에 대한 값을 찾을때 상수시간에 접근할 수 있도록 해준다. 또한 HashMap은 크기가 동적으로 조절된다. 이는 요소를 추가하거나 제거할 때마다 배열의 크기를 조정해줘, 공간을 효율적으로 활용할 수 있게 도와준다.
이런점을 이용해서 새롭게 코드를 짜봤다.
class Solution {
fun solution(players: Array<String>, callings: Array<String>): Array<String> {
val playerMap = players.withIndex().associate { it.value to it.index }.toMutableMap()
for (i in 0 until callings.size) {
val playerIndex = playerMap[callings[i]] ?: continue
//선수가 이미 1등이라면 진행할 필요 없기 때문.
if (playerIndex > 0) {
val winPlayer = players[playerIndex]
val losePlayer = players[playerIndex - 1]
players[playerIndex - 1] = winPlayer
players[playerIndex] = losePlayer
//해시맵 업데이트해서 교환된 선수의 인덱스를 갱신해주기
playerMap[winPlayer] = playerIndex - 1
playerMap[losePlayer] = playerIndex
}
}
return players
}
}players.withIndex()를 이용해서 배열의 각 요소에 대해 인덱스와 함께 값을 가져올수 었다. accociate함수를 이용해서 생성된 키와 값을 사용해서 맵을 생성하는데, 람다식에서 it.value는 배열의 요소(선수들의 이름), it.index는 해당 요소의 인덱스이다. 따라서, 각 선수들의 이름을 키(Key)로 하고, 그에 해당하는 인덱스를 값(Value)으로 하는 맵을 생성시켜줬다.
이 후에, 호출된 선수의 인덱스를 가져와 해당선수의 순위를 그 앞 인덱스를 가지고있는 선수와 순서를 바꿔주고 맵을 업데이트해서 실행시간을 줄일 수 있었다.
이 문제를 풀면서 String형식으로 이루어진 배열은 HashMap을 이용해서 해당 String을 키(Key)값으로 만들어 준다면 어떤 문제든, 시간복잡도를 줄여 더 효율 좋은 코드를 만들 수 있다고 생각했고, 앞으로 잘 활용해 볼 예정이다.
