프로그래머스 문제 시간복잡도 최적화(달리기 경주, 스킬트리, 할인 행사)

 

썸네일용 이미지

 

 

프로그래머스의 문제 포스팅
해당 포스팅 문제들은 (주)그렙이 저작권을 가지고 있습니다.
(지문 하단에 별도 저작권 표시 문제 제외)
해당 포스팅은 코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보를 비상업적, 비영리적 용도로 게시했습니다.

 

 

2024년 하반기 취업준비 시즌 중 원하는 기업의 서류통과 이후 코딩테스트가 잡혔다. 그런데 언어 제한이 python3와 C로만 제한되어 있어서.. 급하게 원래 하던 C++을 잠시 두고 python으로 코딩테스트를 일주일 남짓한 기간동안 준비해야 했다.

 

lv1부터 제출수는 많은데, 정답률은 낮은 문제들을 집중적으로 골라풀어보는 식으로 테스트 전까지 40문제정도만 풀고 시험에 임할 생각이다.. 그 중 몇 문제들을 풀어본 뒤, 풀이 최적화 과정을 포스팅하고자 한다.

 

 

1. 달리기 경주

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

프로그래머스

 

callings의 길이가 1,000,000이하이고 players의 길이는 50,000이하이다.

loop 깊이를 2까지 내려가는 순간 최악의 경우 50,000 * 1,000,000 = 50,000,000,000번 (500억번연산..)이다.

보통의 코딩테스트 플랫폼에서 언어별 시간보정을 제공하는것으로 알려져있다.

따라서 1초당 1억번으로 생각하고 복잡도를 고려하면 되는데, 해당 문제를 단순히

반복문을 돌면서 swap을 하는 식으로 풀면 무조건 시간초과이다.

이를테면 이런 코드..

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

 

문제는 index()는 배열을 처음부터 끝까지 순회하면서 원하는 요소를 찾는다.. 결국 players의 길이가 50,000

그리고 이게 callings모든 요소를 반복하니 위 코드로는 절대 통과할 수 없는 것이다.

 

반드시 그런것은 아니지만, python의 경우 시간복잡도 개선을 위해서 dict자료구조를 많이 사용하는 것 같다.

딕셔너리는 해시 테이블 기반이라 평균적으로 O(1) 시간에 검색, 삽입, 삭제가 가능하기 때문이다.

 

코드로 나타내면,

 

player.index(call)

 

를

player_ranks[call]

 

 

이렇게만 해도 O(1)으로 즉시 등수를 찾을 수 있다. 즉 callings의 길이 O(n)정도로 시간을 줄일 수 있는 것이다.

 

번외로..

위 방법은 추가 메모리를 사용하는 대신 시간을 줄이는 기법이다

공간을 사용해서 시간을 번다고 할 수 있고, 약간의 추가 메모리로 연산 속도를 극적으로 향상시키는 아주 간단한 코드 사례로 볼 수 있겠다.

 

 

최적화된 풀이

def solution(players, callings):
    player_ranks = {player: rank for rank, player in enumerate(players)}
    
    ranks = {rank: player for rank, player in enumerate(players)}
    
    for call in callings:
        current_rank = player_ranks[call]
        front_rank = current_rank - 1
        front_player = ranks[front_rank]
        
        # 등수 교환
        players[current_rank], players[front_rank] = players[front_rank], players[current_rank]
        
        # 딕셔너리 업데이트
        player_ranks[call] = front_rank
        player_ranks[front_player] = current_rank
        ranks[front_rank] = call
        ranks[current_rank] = front_player
    
    return players

 

 

파이썬을 너무 오래 안써서 그런지 컴프리헨션 코드보다 아래 코드가 더 눈에 잘 들어오는 것 같아서 풀어 써본 버전

 

def solution(players, callings):
    player_ranks = {}

    ranks = {}

    for rank, player in enumerate(players):
        player_ranks[player] = rank
        ranks[rank] = player
    
    for call in callings:
        current_rank = player_ranks[call]
        front_rank = current_rank - 1
        front_player = players[front_rank]
    
        # 선수 위치 교환
        players[current_rank], players[front_rank] = front_player, call
    
        # 딕셔너리 업데이트
        player_ranks[call] = front_rank
        player_ranks[front_player] = current_rank
    
    return players

 

2. 스킬트리

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

프로그래머스

 

 

3. 할인 행사

 

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

프로그래머스

 

위 문제도 문제를 읽다보면 주어진대로 반복문을 돌면서 슬라이싱을 하고싶은 충동이 느껴진다.

이를테면 아래 코드처럼

def solution(want, number, discount):
    answer = 0
    
    for i in range(len(discount) - 9):
        can_buy = True
        for j in range(len(want)):
            if discount[i:i+10].count(want[j]) < number[j]:
                can_buy = False
                break
        if can_buy:
            answer += 1
    
    return answer

 

이렇게 직관적으로 짜버린다음에 제출하면 통과이다. 

(number의 원소 개수가 10이하, discount의 길이가 100,000이하이기 때문..)

 

하지만, number가  10,000이고 discount의 길이가 1,000,000이라면??

 

좀 더 최적화된 풀이를 고안해야 한다.

 

최적화한 풀이

 

from collections import Counter

def solution(want, number, discount):
    answer = 0
    want_dict = dict(zip(want, number))
    want_count = sum(number)
    
    current_items = Counter(discount[:10])
    
    if current_items == Counter(want_dict):
        answer += 1
    
    for i in range(len(discount) - 10):
        current_items[discount[i]] -= 1
        if current_items[discount[i]] == 0:
            del current_items[discount[i]]
        
        current_items[discount[i+10]] = current_items.get(discount[i+10], 0) + 1
        
        if current_items == Counter(want_dict):
            answer += 1
    
    return answer