문제 분석
요약 | 선수들의 이름이 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>
풀이
전개 순서
- 선수 목록(players)을 인덱스와 함께 별도의 map(playerMap)에 저장한다.
- 불린 선수 목록(callings)를 순회하면서
- 현재 불린 선수의 순번을 기억해둔다(idx)
- 그 앞 순번 선수의 이름을 기억해둔다(prevPlayer)
- 앞 선수 변경 처리
5-1. playerMap에서 앞 선수의 순번을 현재 불린 선수의 순번으로 바꿔준다.
5-2. players 배열에서 앞 선수의 위치에 현재 불린 선수로 바꿔준다. - 현재 선수 변경 처리
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]
