심심해서 백준 말고 프로그래머스를 풀어봤는데 난관에 봉착해 버렸다.
심심풀이로 하려다가 공부를 한 꼴이 됐다.
처음엔 시간복잡도 신경 안쓰고 엥? 쉽네~ 이러고 그냥 코딩했다.
def solution(players, callings):
for i in callings:
idx = players.index(i) # 요것이 시간초과의 주범!
players[idx-1], players[idx] = players[idx], players[idx-1]
return players하지만...! 무참히 시간 초과
위의 시간복잡도는 players의 길이를 n, callings의 길이를 m이라고 할 때, O(nm)을 가진다. 50,000 * 1,000,000....
즉, 어마어마하다는 것
인덱싱에 문제가 있는 것은 알았지만 어떻게 해야 빠르게 하는지 전혀 몰랐기에 30분을 넘어갈 무렵 문제 이름 그대로 검색했고 그 과정을 통해 구현된 코드는 이렇다.
def solution(players, callings):
p_dic = {v:i for i, v in enumerate(players)}
for i in callings:
front, back = p_dic[i]-1, p_dic[i]
p_dic[players[front]], p_dic[players[back]] = back, front
players[front], players[back] = players[back], players[front]
return players딕셔너리는 해쉬 테이블을 사용하기 때문에 O(1)이라는 빠른 시간을 자랑하며,
그로 인해 O(m)으로 시간 복잡도를 줄일 수 있다.