프로그래머스 Lv 1. 달리기 경주
처음 해당 문제를 접근하였을 때, 우선 for문을 사용하겠구나라는 생각과 함께 'callings'로 불러오는 것의 index값을 알아야겠다고 생각을 했었다.
첫번째 풀이 방법
- callings의 첫번째 값을 가져와서 players에서 몇번째에 위치하는지 파악한다.
- players 배열에서 확인한 위치의 앞에 있는 값과 변경한다.
- 이를 callings의 갯수만큼 반복한다.
func solution(_ players:[String], _ callings:[String]) -> [String] {
// 현재의 순위는 입력받은 players의 순서
// callings의 count를 생각하고 그 때마다 순위를 변동한다.
var raceInProgress: [String] = players // race의 과정의 순위
var raceResult: [String] = [] // race의 결과를 넣기 위한 배열
for i in 0..<callings.count {
// callings에서 불린 player의 순위를 확인한다.
if let callingRanking = raceInProgress.firstIndex(of: callings[i]) {
let changeRank = raceInProgress[callingRanking]
raceInProgress[callingRanking] = raceInProgress[callingRanking-1]
raceInProgress[callingRanking-1] = changeRank
}
}
raceResult = raceInProgress
return raceResult
}위와 같은 순서로 진행을 했을 때 test코드로는 정상적으로 결과값이 나왔다. 하지만 실제로 제출을 했을 때, 시간초과를 보게되었다. 정확하게 어떻게 문제인지를 파악하지 못했다. 다른 팀원분의 피드백을 받게 되었는데, 시간 복잡도(Time Complexity)에 대해서 검색을 한번해보라고 하셨고, 우선 해당 문제에 대해서는 다음과 같은 이야기를 해주셨다.
for문안에 firstIndex를 쓰는 것은 이중 for문을 사용하는 효과와 같아 그 시간이 제곱으로 걸리기 때문에 이를 쓰지말고 해결해보라고 하셨다.
그렇다면.. 어떻게 풀어야할까?라는 고민을 하게 되었다.
그래서 든 생각은 처음부터 players의 이름과 등수를 모두 저장을 하는 것이 어떨까라는 생각을 하게 되었다.
두번째 풀이 방법
- Dictionary를 이용해서 players의 이름과 랭킹을 각각의 기준으로 변수에 저장한다.
- 이름을 key로 설정한 Dictionary에서는 callings에서 불려진 사람의 순위,
랭킹을 key로 설정한 Dictionary에서는 불려진 사람의 앞사람 이름을 얻어온다. - 불려진 사람의 순위는 -1이되고, 앞사람의 순위는 불려진 사람의 원래 순위로 바꾸어ㅓ 저장한다.
- 마지막으로는 랭킹을 key로 설정한 Dictrionary를 key의 순서대로 다시 정렬하여 결과를 표시한다.
func solution(_ players: [String], _ callings: [String]) -> [String] {
var rankToName = [Int: String]()
var nameToRank = [String: Int]()
var raceResult: [String]
// 이름과 랭킹을 같이 기록
for (index, player) in players.enumerated() {
rankToName[index+1] = player
nameToRank[player] = index+1
}
for caller in callings {
if let callerRank = nameToRank[caller], let frontName = rankToName[callerRank - 1], callerRank > 1 { // 불려진 사람의 순위, 앞에 사람의 이름
// 불린 사람의 순위는 -1이 되고 (callerRank-1등은 caller)
rankToName[callerRank - 1] = caller
nameToRank[caller] = callerRank - 1
// 원래 불린 사람의 앞에 있는 사람은 불린 사람의 순위가 된다. callRank등은 frontName
rankToName[callerRank] = frontName
nameToRank[frontName] = callerRank
}
}
// 마지막으로 등수 순으로 정렬을 한다.
raceResult = rankToName.sorted{ $0.key < $1.key }.map{ $0.value}
return raceResult
}결과적으로 Dictionary를 사용하여 firsIndex를 사용하여 0부터 동일한 값이 나올때까지 데이터를 찾는 시간을 소비하는게 아니라 해당하는 key값의 value값을 얻어오는 형식을 사용하니까 결과적으로는 시간초과 에러가 발생하지 않았다.
이번에 느낀점
시간 초과라는 에러를 보고나서 시간 복잡도라는 개념이 있다는 것을 이번 기회에 알게 되었다. 그리고 Apple 공식 문서를 보니 firstIndex에서도 시간 복잡도라는 개념이 표시되어있는 것 또한 확인하였다! 알고리즘을 풀이할 때 이러한 것을 고려하여 풀다보면 어느새 나도 적응이 되어 어디에나 적용을 할 수 있지 않을까 하는 고민을 하게 되었다.
추가적으로 해당 개념에 대한 정리를 진행할 것이다.
1. 시간 복잡도(Time Complexity)
2. Dictionary
