[코딩 테스트 합격자 되기 - 11주차] 시뮬레이션(Simulation)

뭔가 시뮬레이션은 어떻다기 보다는 많은 문제를 접하면서 내 생각대로 문제를 풀 수 있을까가 많이 중요해보임. 그렇기 때문에 기초가 더 중요한 챕터라고 생각함.

 

문제 65 - 이진 변환 반복하기

프로그래머스

def solution(s):
    # [1] 0을 제거한 횟수, 2로 변환한 횟수
    cnt_rm = cnt_2 = 0
    
    # [2] s가 '1'이 아닌 동안 계속 반복
    while s != "1" :
        # [3] 이진 변환 횟수 1 증가
        cnt_2 += 1
        # [4] s에서 '0'의 개수를 세어 cnt_rm 에 누적
        cnt_rm += s.count("0")
        # [5] s에서 '1'의 개수를 세고, 이를 이진수로 변환
        # bin() 함수를 사용하기 위해 0b 뒤의 문자열 활용
        s = bin(s.count("1"))[2:]
    
    # [6] 이진 변환 횟수와 제거된 모든 '0'의 개수를 리스트에 담아 반환
    return [cnt_2, cnt_rm]

1. 2진수에서 0을 제거
2. 0을 제거한 2진수의 길이를 다시 2진수로 표현
3. 과정 2에서 표현한 2진수가 1이 아니면 이진 변환 결과를 가지고 과정 1부터 반복

bin()함수를 활용하여 s를 이진수로 표현. 이때 앞에 '0b'가 붙어서 나오기 때문에 앞에서 2번째 문자를 생략한 문자열을 받아오는 것을 유도하였음.

 

문제 66 - 롤케이크 자르기

프로그래머스

 

from collections import Counter

# topping 배열을 입력으로 받아서, 피자를 나눌 수 있는 경우의 수를 반환하는 함수
def solution(topping):
    split_cnt = 0  # 피자를 나눌 수 있는 경우의 수를 저장할 변수
    topping_cnt = Counter(topping)  # 각 토핑의 개수를 계산하여 저장
    half_topping_set = set()  # 현재까지 고려된 토핑의 종류를 저장할 집합
    
    # 피자 토핑 배열을 순회
    for t in topping:
        half_topping_set.add(t)  # 현재 토핑을 집합에 추가
        topping_cnt[t] -= 1  # 현재 토핑의 개수를 하나 줄임

        if topping_cnt[t] == 0:  # 만약 현재 토핑의 개수가 0이 되면,
            topping_cnt.pop(t)  # 해당 토핑을 카운터에서 제거

        # 왼쪽 부분(현재까지 고려된 토핑의 종류)과 오른쪽 부분(나머지 토핑의 종류)의 토핑 종류 수가 같다면
        if len(half_topping_set) == len(topping_cnt):
            split_cnt += 1  # 나눌 수 있는 경우의 수를 하나 증가시킴
            
    return split_cnt  # 나눌 수 있는 경우의 수 반환

케이크를 자른 부분을 기준으로 왼쪽은 철수, 오른쪽은 철수 동생의 것이 되는데 자른 부분을 기준으로 왼쪽 숫자와 오른쪽 숫자가 무엇인지 반복문으로 검사하면 매우 비효율적이다. 이것을 효율적으로 개선할 방법에 대해 생각해보자. 

케이크를 자르면 동생의 토핑 개수를 줄이고 형이 먹을 케이크는 set()으로 관리하여 중복 토핑은 없는 것으로 생각한다. 그리고 동생의 토핑 개수가 0이 되는 종류가 생기면 동생이 먹을 케이크에서 제외한다. 그렇게 하다 보면 형의 토핑 종류와 동생 토핑 종류가 같은 순간이 온다. 같은 순간에 공평함 포인트를 1 늘리면 된다. 

 

1. split_cnt 변수 선언
2. topping_cnt는 각 토핑의 개수를 가지는 변수이고 Counter객체를 활용하여 계산함
3. topping_set은 케이크를 자르면서 철수가 먹을 토핑을 저장할 변수 => set()으로 처리
4. 첫 번째 토핑부터 시작해서 한 칸씩 이동하며 케이크를 자르면서 진행
5. 새 토핑은 topping_set에 추가하고 추가한 토핑은 topping_cnt에서 제거
6. 만약 topping_cnt에서 0이 되는 토핑이 있다면 pop(t)로 목록에서 제거한다.
7. topping_set과 topping_cnt의 원소 개수가 같으면 split_cnt += 1을 한다.
8. 연산이 끝이 나면 return 한다.

N은 topping의 길이이다. topping의 길이만큼 반복문을 수행하므로 시간 복잡도는 O(N)이다. 따라서 최종 시간 복잡도는 O(N).

 

시뮬레이션의 경우, 탄탄한 기초를 바탕으로 아이디어를 잘 구상한 다음, 코드로 잘 옮겨적는것이 포인트인 챕터라고 생각한다. 그렇기 때문에 앞에서 공부하였던 자료구조 및 알고리즘을 잘 구현하는 것이 중요하다.