[프로그래머스] 달리기 경주

문제 분석

달리기 경주

요약 | 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하라

Input data :

• players: Array<String>
  • 5 ≤ players의 길이 ≤ 50,000
  • players[i]는 i번째 선수의 이름을 의미합니다.
  • players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • players에는 중복된 값이 들어가 있지 않습니다.
  • 3 ≤ players[i]의 길이 ≤ 10
• callings: Array<String>
  • 2 ≤ callings의 길이 ≤ 1,000,000
  • callings는 players의 원소들로만 이루어져 있습니다.
  • 경주 진행중 1등인 선수의 이름은 불리지 않습니다.

선수가 최대 5만명, 부르는 횟수는 최대 100만으로 상당히 긴 데이터가 들어올 수도 있어 처리 시간에 유의해야 한다.

Output data :

Array<String>

풀이

전개 순서

1. 선수 목록(players)을 인덱스와 함께 별도의 map(playerMap)에 저장한다.
2. 불린 선수 목록(callings)를 순회하면서
3. 현재 불린 선수의 순번을 기억해둔다(idx)
4. 그 앞 순번 선수의 이름을 기억해둔다(prevPlayer)
5. 앞 선수 변경 처리
   5-1. playerMap에서 앞 선수의 순번을 현재 불린 선수의 순번으로 바꿔준다.
   5-2. players 배열에서 앞 선수의 위치에 현재 불린 선수로 바꿔준다.
6. 현재 선수 변경 처리
   6-1. playerMap에서 현재 불린 선수의 순번을 -1 처리해준다.
   6-2. players 배열에서 현재 불린 선수의 위치를 한칸 앞으로 바꿔준다.

Data type :

MutableMap<String, Int>

• '검색' 연산에 있어서 키 값만 찾으면 되는 Map이 더 효율적이다.
• 삽질 TIM
  • 처음에는 (무지성으로) List를 사용했었다. indexOf()와 같은 메소드를 끌어와 쓰다보니 처리 속도가 오래 걸렸고 fail을 받았다.
  • 그 이후에는 Array를 사용했었다. indexOf() 같은 것을 쓰지 않고 임시 변수에 현재 값을 저장해뒀다가 앞의 선수와 바꿔치기 해주는 식으로 코드를 작성했었다. 다만 이 방법을 사용하려니 for문을 2중으로 사용하게 되었고 불필요하게 모든 선수 목록을 다 순회하면서 calling된 선수를 찾느라 시간초과로 fail을 받았다.

코드

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {        
        val playerMap = mutableMapOf<String, Int>()
        players.forEachIndexed { index, value -> playerMap[value] = index}       
        callings.forEach { call ->
            val idx = playerMap[call]!! //현재 인덱스
            if (idx > 0) {
                val prevPlayer = players[idx - 1] //앞 선수의 이름
                playerMap[prevPlayer] = idx //앞 선수의 순번을 불린 선수 것으로 변경
                players[idx] = prevPlayer //배열상 앞 선수의 위치를 불린 선수 위치로 변경                
                playerMap[call] = idx - 1 //불린 선수의 순번에서 1 빼기
                players[idx - 1] = call //배열상 불린 선수의 위치를 한칸 앞으로 변경
            }
        }
        return players
    }
}

---

[TIL-240327]