[프로그래머스] 달리기 경주 Lv.1 8,9,10,11,12,13 시간 초과 해결 #python

	프로그래머스 문제풀이		python
			No. 달리기 경주

 

 

#파이썬 #프로그래머스 #문제풀이 #Lv.1 달리기 경주

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

프로그래머스

 

8,9,10,11,12,13 실패 (시간 초과) 해결

 

index 검색 최적화 하는 방법에 집중한다.

 

 

 

---

// 알고리즘

가장 중요한 목적이 무엇인지?

일단 .index()함수를 사용하여 간단한 코드를 작성했다.

 

def solution(players, callings):
    answer = players
    
    for i in range(len(callings)):
        j = players.index(callings[i])
        players[players.index(callings[i])-1],players[j] = players[j],players[j-1]
    
    return answer

 

단순하게 index를 찾아 앞뒤로 바꾼다고 생각해보면 테스트 8,9,10,11,12,13에서 시간 초과가 뜬다.

아무래도 .index() 같은 경우 앞에서 부터 선형 탐색하여 발견한 가장 먼저의 index : player[50000]에서 일을 처리하고, callings[1000000]만큼 반복하니까 O(n^2)임으로 최악의 경우 50000*1000000 = 5백억의 연산으로 시간 초과이다.

 

따라서 한 번에 찾는 것이 중요하다.

 

 

 

왜 이런 방법을 선택했는지?

 

한 번에 찾으면 callings[1000000] 만큼 앞뒤로 바꿔주는 swap 한 번만 진행하면 O(n)의 연산이다.

한 번에 찾는 방법은 값에 대한 index를 아는 경우, 아니면 딕셔너리(해쉬)를 사용하는 경우를 생각해 볼 수 있다.

따라서 dictionary를 사용하기로 했다.

 

 

 

 

// 구현하기

-> How?

어떻게 구현?

dictionary는 중복되는 값이 없는 경우만 가능하다. {"mumu": 1 , "mumu": 2} 로 저장하면 "mumu": 2만 남게 된다.

 

list를 dictionary로 변경하는 법 (list to dict)

파이썬 내장함수 enumerate()함수를 사용하면 index와 원소를 동시 접근하면서 루프를 돌릴 수 있다. 위 처럼 작성하면 등수에 맞게 만들 수 있다. 해당 함수는 튜플을 만들어준다.

 

그러나 .get()함수로 calling을 사용해서 등수를 찾으면. 이 등수로 결국엔 출력해야하므로 value를 총해서 key를 찾아야 한다. 따라서 뒤집어서 양쪽으로 만들어주고 연결하는 방법을 사용했다.

 

 

 

 

->Why?

왜 이런 방법을?

 

구현하다보니, value를 통해 key를 찾는 방법이 필요했다.

---

// 완성코드

def solution(players, callings):
    dic_str_i = {str : i for i,str in enumerate(players)}
    dic_i_str = {i : str for i,str in enumerate(players)}
    answer = []
        
    for i in range(len(callings)):
        j = dic_str_i.get(callings[i]) # 등수가 나온다
        dic_str_i[dic_i_str.get(j-1)] = j
        dic_str_i[callings[i]] = j-1
        
        dic_i_str[j] = dic_i_str.get(j-1)
        dic_i_str[j-1] = callings[i]
        
    #등수순으로 출력해야함
    for i in range(len(dic_i_str)):
        answer.append(dic_i_str.get(i))

    return answer