[알고리즘연습] 콜라병, 달리기경주

 

콜라병

 

LV1, https://school.programmers.co.kr/learn/courses/30/lessons/132267

# 0505 15:50 - 16:04


def solution(a, b, n):
    count = 0
    while n>=a:
        A = (n // a)*b 
        B = n % a
        count += A
        n = A+B

    answer = count
    return answer

 

 

달리기경주

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

 

 

계속 시간복잡도 초과 

#0505 16:12 16:50 -> 시간초과 케이스 발생 

# 시간복잡도 초과

def solution(players, callings):
    rank = {} #{player:rank}
    for i,player in enumerate(players):
        rank[player] = i

    for call in callings:
        target = [k for k,v in rank.items() if v == (rank[call]-1)] # 바뀔 번호 
        rank[call] -= 1 # rank-1
        rank[target[0]] +=1 # player rank +1 

    # sort 
    rank = sorted(rank.items(), key = lambda x:x[1], reverse=False)
    answer = [k[0] for k in rank]
    return answer


# - 17:11
# 수정 코드 -> 여전히 시간초과 몇케이스

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


# 시간복잡도 초과 
def solution(players, callings):
    for i, call in enumerate(callings):
        index = players.index(call)
        
        # 새로운 리스트를 매번 만드는 방식 
        players = players[:index-1] + [call] + [players[index-1]] + players[index+1:]
    
    answer = players
    return answer

최종 통과코드 

def solution(players, callings):
    rank = {} #{player:rank}
    for i,player in enumerate(players):
        rank[player] = i

    for call in callings:
        called, target = rank[call], rank[call]-1
        rank[players[called]] = target
        rank[players[target]] = called
        
        #players 순서 한번에 바꿔주기 
        players[called], players[target] = players[target], players[called]
    
    answer = players
    return players