99클럽 코테 스터디 26일차 TIL : 시뮬레이션

박지원·2024년 8월 16일

99클럽 알고리즘

99클럽 코테 스터디

목록 보기

22/25

오늘의 학습 키워드

시뮬레이션

구현과 시뮬레이션

코딩 테스트에서 구현이란 생각을 코드로 바꾸는 과정으로, 시뮬레이션은 구현 카테고리 중 하나이다.
구현 문제의 대표적인 예는 완전 탐색과 시뮬레이션이 있다.

완전 탐색

문제를 해결할 때 될 수 있는 모든 경우를 고려하여 정답을 찾는 걸 의미
n개의 숫자 중 m 개의 숫자를 적절히 골라 합이 최대가 되도록 해야 한다면, 두 숫자의 합이 될 수 있는 모든 경우의 수 중 최대 값을 찾게 되는데 이를 완전탐색이라 한다
for문을 사용한 완전탐색, 재귀를 사용한 완전 탐색이 존재

시뮬레이션

문제에서 주어진 조건대로 특정 작업을 수행하는 걸 의미
주로 2차원 리스트 형식으로 많이 주어진다

참고한 블로그

데크

양방향 큐로,앞 뒤 방향에서 요소를 추가하거나 삭제할 수 있다
양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상자료형
리스트의 pop(0) 은 시간복잡도가 O(n) 인데, 데크의 popleft는 O(1)

from collections import deque

deq = deque()

# Add element to the start
deq.appendleft(10)

# Add element to the end
deq.append(0)

# Pop element from the start
deq.popleft()

# Pop element from the end
deq.pop()

# 주어진 리스트를 데크의 오른쪽에 추가
deq.extend(array)

# 주어진 리스트를 데크의 왼쪽에 추가
deq.extendleft(array)

#item 을 데크에서 찾아 삭제
deq.remove(item)

#해당 deque 전체 삭제
deq.clear()

#역순으로 정렬
deq.reverse()

#데크를 Num 만큼 회전 ( 양수면 오른쪽, 음수면 왼쪽 )
#deque.rotate(num)

공부한 내용 본인의 언어로 정리하기

프로그래머스 달리기 경주

첫번째 시도

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

시간 초과

두번째 시도

from collections import deque
def solution(players, callings):
    callings = deque(callings)
    players = deque(players)  
    
    while callings:
        name = callings.popleft()
        idx = players.index(name)
        
       
        players[idx] = players[idx - 1]
        players[idx - 1] = name
    
    return list(players)

리스트보다 데크를 사용했을 때 시간복잡도가 작아진다는 것을 떠올리고 deque 을 사용해 구현
채점 결과
정확성: 68.8
합계: 68.8 / 100.0

그래서 질문을 확인해보니 index() 함수의 실행복잡도가 오래걸렸다

세번째 시도 -> 통과



def solution(players, callings):
    player_index = {player: i for i, player in enumerate(players)}  
    
    for name in callings:
        current_idx = player_index[name]  
        if current_idx > 0:
            prev_player = players[current_idx - 1]
            players[current_idx],players[current_idx - 1] = players[current_idx - 1] ,players[current_idx]
        player_index[name] -= 1
        player_index[prev_player] += 1
    return players

딕셔너리를 사용해 이름:index 형식으로 만들었다
players를 swap 해주고
player_index를 수정해주는 로직으로 진행하였다

다른 사람의 풀이


def solution(players, callings):
    pla_dic = {key: i for i, key in enumerate(players)}

    for p in callings:
        c = pla_dic[p]
        pla_dic[p] -= 1
        pla_dic[players[c-1]] += 1
        players[c-1], players[c] = players[c], players[c-1]

    return players

Q: 딕셔너리가 뭐길래 시간복잡도를 해결하지?

index() 메서드는 O(n) 의 시간복잡도가 소요된다
딕셔너리는 해시 테이블을 사용해 구현되므로, 평균 O(1) 의 시간복잡도를 가진다
프로그래머스 질문 게시판에 더 상세한 설명이 나와있었다

callings 배열(크기:M)과 players 배열(크기:N)의 크기에 비례하기 때문에 시간복잡도는 둘의 곱인 O(MN)이 되어 이 방법으로 풀 수 없습니다. 일반적으로 O(n)에서 n의 값이 1억을 넘으면 통과가 어렵다고 보면 되는데, 문제 조건을 보면 백만*5만=5백억이라는 수가 나오죠. 이 문제는 양방향 인덱싱을 이용해야 하고, 그러기 위해선 딕셔너리 두 개 또는 딕셔너리 하나와 리스트 하나가 필요합니다.

리스트와 딕셔너리 시간복잡도 비교