[Algorithm] Swift 프로그래머스 달리기경주(178871번)

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

 

문제 접근 

 

callings배열에는 해설진이 부른 선수이름이 들어감. players 배열은 지금 달리고 있는 선수들의 순서임.

 

callings배열에 이름이 들어가 있다면 players 배열의 index를 기준으로 index-1가 되는 것임.

 

앞선수를 추월했기 때문에!! 

 

위 생각을 바탕으로 callings 배열의 순환하면서 

 

player배열에서 callings배열에서 불린 player의 이름이 몇 번째 index에 존재하는지 찾고 

 

그 후 player배열에서 찾은 index 위치에 있는 값을 삭제해 줌!

 

그리고 index값에 -1을 해주어서 배열의 앞쪽으로 이동하게 해 주면 될 거 같았음!!

 

말로만 하면 어려울 수 있으니깐!!  🔽

위와 같이 구현하면 좋을 거 같다고 생각했음.

 

마지막으로 바뀐 순서를 저장하는 배열을 새로 만들지 않아도 되니깐 시간도 많이 걸리지 않을 것 같다고 생각함.

 

 

 

정답풀이 

 

아래와 같이 코드를 구현해 보았음. 

 

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    
    var player = players
    
    // callings 베열에서 player를 찾는다.
    for calling in callings {
        
        // player 배열에서 같은 이름을 가진 player의 index를 찾고
        let index = player.firstIndex(of: calling)!
        // player 배열에서 삭제
        let removedPlayer = player.remove(at: index)
        // player 배열에 index - 1한 만큼 줄여서 다시 넣어주기
        let newIndex = max(0, index-1)
        player.insert(removedPlayer, at: newIndex)
    }
      // 최종적으로 player배열을 return
    return player
}

 

 

하지만 코드를 제출하니깐 테스트 케이스에서 시간초과가 발생하였음!! 

 

새로운 배열을 만들어주지 않아서 시간초과가 없을 거 같았는데 초과가 나서 당황스러웠음. 

 

여러 가지 방법을 알아보다가 swapAt(_:_:)를 알게 됐었음!! 

 

 

컬렉션의 지정된 인덱스에 있는 값을 교환합니다.라고 함. 

 

매개변수

• i - 교환할 첫 번째 값의 인덱스입니다.
• j  - 바꿀 두 번째 값의 인덱스입니다.

예를 들자면 아래와 같음!! 

var arr = [1,2,3,4]
arr.swapAt(0, 3) // [4, 2, 3, 1]

 

arr 배열에 0번과 3번의 값을 교환해주고 있음!! 

 

swapAt(_:_:)를 이용해서 다시 코드를 구성해 보았음!! 

 

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var players = players
    for calling in callings {
        let index = players.firstIndex(of: calling)!
        players.swapAt(index-1, index)
    }
    return players
}

 

여기서!! var players = players로 같은 이름으로도 변수 선언이 가능하다는 것은 알았음!! 

 

맨 처음 했던 방식은 player 배열에서 삭제하고 다시 index-1의 위치에 넣어주었는데 

 

swapAt(_:_:)를 이용해서 players 배열에서 불러진 player의 index값을 찾으면 

 

players.swapAt(index-1, index)로 index-1의 위치인 player와 교환해 주게 구현을 했음!! 

 

하지만..... 

 

 

다시 시간초과로 실패하였음!! 

 

많은 고민을 했지만 해결방법을 찾지 못해서 다른 분의 코드를 참고하였음!! 

 

 

정답코드

 

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var rank = [String: Int]()
    var players = players
    
    for i in 0..<players.count {
        rank[players[i], default: 0] = i
    }

    for calling in callings {
        let index = rank[calling]!  // 현재 호출된 선수의 등수
        let player = players[index-1] // 앞 선수
        
        rank[calling]! -= 1        // 호출된 선수의 등수를 -1
        rank[players[index-1]]! += 1  // 앞 선수의 등수를 +1
        
        players.swapAt(index, index-1)
    }

    return players
}

 

코드를 보니깐 이제야 아!! 딕셔너리로 하면 되네!!라는 생각이 들었음!! 

 

다른 분들도 배열로 접근했다가 시간 초과가 걸리신 분들이 많은 거 같았음.

 

그럼 왜?? 나의 풀이는 시간초과가 걸렸을까?? 

 

player.firstIndex(of: calling)! 때문인 거 같음!!!

 

 

컬렉션에서 지정된 값이 나타나는 첫 번째 인덱스를 반환합니다.라고 함!! 

 

firstIndex(of:)는 배열의 앞에서부터 조회해서 첫 번째 일치하는 값은 index를 반환하게 됨!

 

배열의 길이가 n이라고 할 때 O(n)의 시간이 걸림.

 

calling에 대해 firstIndex(of:)를 호출하는 것은 O(n) 시간이 걸리고,

 

이 작업을 callings 길이 m번 반복하므로 전체 시간 복잡도는 O(m * n)이 됨!!

 

그래서 시간초과가 걸린 것 같음!!

 

그럼 왜?? 딕셔너리는??🤔

 

딕셔너리는 순서가 없고 해시 테이블이기 때문인데!! 

 

특정 Key - Value를 저장한다고 하면 

 

해당 Key를 해시함수를 통해 해시를 하고, 결과 값인 해시 주소 값에 해당하는 해시 테이블 슬롯에 Value를 저장하는 것임! 

 

즉!!! 배열은 원하는 값을 찾기 위해 0번 index부터 순회하기 때문에 시간 복잡도가 O(n)

 

딕셔너리는 Key값을 해시하여 바로 index에 접근하기 때문에 O(1)이 나옴!!

 

딕셔너리가 배열보다 빠르다는 말임!! 

 

다시 정답코드로 돌아가 보면!! 

 

var rank = [String: Int]()
    var players = players
    
    for i in 0..<players.count {
        rank[players[i], default: 0] = i
    }

 

rank라는 딕셔너리에 players 배열에서 주어진 등수(index)를 Value 값으로 넣어주고 있음.

 

 for calling in callings { 
        let index = rank[calling]!  // 현재 호출된 선수의 등수
        let player = players[index-1] // 앞 선수
        
        rank[calling]! -= 1        // 호출된 선수의 등수를 -1
        rank[players[index-1]]! += 1  // 앞 선수의 등수를 +1
        
        players.swapAt(index, index-1)
    }

 

callings 배열을 순환하면서 불린 선수의 등수(index)를 찾고, 이름 불린 선수의 앞 선수를 찾음! 

 

 그 후 딕셔너리에서 호출된 선수의 등수에서 -1을 해주고 

 

앞서 있는 선수의 등수를 +1을 해줌!! 

 

마지막으로 위에서 알아본 swapAt(_:_:)를 이용해서 

 

players 배열에서 index 위치의 값과 index-1 위치의 값을 교환해 주었음!!

 

 

 

배열과 딕셔너리의 정확한 차이를 다시 알게 해 준 문제였음!! 

 

 

 

 

 

참고 및 인용 

 

https://developer-eddy403.tistory.com/120