달리기 경주 | 프로그래머스

김태영·2024년 6월 4일

목록 보기

10/33

📍 달리기 경주

💡 문제

해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다.

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

⚠️ 제한사항

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

✅ 풀이

👆 첫 번째 풀이 (실패)

우선 제한사항을 신경쓰지 않고 풀어보았다.

{"선수이름": [불린 이름]} 형태의 Map을 생성
- 해당 맵을 선수 이름으로 접근하면, size를 통해 이름이 불린 횟수를 알 수 있다.
순서를 변경하기 위해 players를 mutableList로 변환
- *를 사용하면 배열을 풀어서 넣을 수 있다.
calls를 돌며 플레이어 리스트에서 이름을 지우고, 원래 위치해 있던 인덱스에서 불린 횟수 만큼을 뺀 인덱스에 다시 삽입한다.
함수 반환형을 맞춰주기 위해 toTypedArray를 사용

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        var calls = callings.groupBy { it }
        var p = mutableListOf<String>(*players)
        
        calls.map { (name, called) ->
            var i = players.indexOf(name)
            var c = called.size
            
            p.remove(name)
            p.add(i-c, name)
        }
        
        return p.toTypedArray()
    }
}

너도 나도 우리 모두 알 것이다. 이 코드는 썩었.. 아니 시간 초과가 발생한다. list는 포인터를 사용해 탐색을 하기 때문에 탐색 성능이 좋지 않다고 한다. 그 대신 앞과 뒤에 어떤 요소가 있는지 알고 있기 때문에 add(삽입할 위치, 값) 같은 삽입이나 삭제 작업을 쉽게 할 수 있다. 위의 풀이는 players라는 배열과 플레이어 리스트를 둘 다 탐색하는 코드이기 때문에 시간이 초과된다.

✌️ 두 번째 풀이 (성공)

사실 감이 안잡혔다. 오케이 배열이 탐색이 빠르니까 배열을 사용해야지! 하고 생각하니 도대체 어떻게 배열로 구현해야하는 건지 너무 막막했다. 작성은 내가 했지만 사실 다른 사람들의 코드를 이거저거 조합해 풀이했다.

검색을 통해 HashMap을 사용하면 빠른 탐색이 가능하다는 정보를 얻게 되었다! 그래서 HashMap은 무엇인고 하니, MutableMap의 한 종류라고 한다. 배열은 인덱스를 통해 값을 찾아 시간 복잡도가 O(n)이지만, Map은 key를 통해 값을 찾기 때문에 시간 복잡도가 O(1)이다!

이제 나는 list보다 배열이, 배열보다 Map이 빠르다는 것을 안다. 선수들의 이름을 key로, 순위를 value로 갖는 Map을 사용해 풀이했다.

그런데 나는 이미 첫 번째 풀이에서 이름이 불린 횟수를 다룰 때 Map을 사용했다. Map을 사용했는데도 시간 초과가 발생한 것을 보니, 선수의 순위를 탐색할 때도 Map을 사용해야 하는가 보다.

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        var p = players.indices.associateBy { players[it] }.toMutableMap()

        callings.map { name ->
            var originRank = p[name]!!
            var frontName = players[originRank - 1]

			// 실제 답이 되는 배열 수정
            players[originRank] = frontName
            players[originRank - 1] = name

			// 변경된 순위 적용
            p[name] = originRank - 1
            p[frontName] = originRank
        }

        return players
    }
}