2023.01.17 코딩 테스트 공부 기록 입니다.

프로그래머스 : 쿼드압축 후 개수 세기

🤡쿼드압축 후 개수 세기 (Lv.2)

🤑풀이

import numpy as np
from collections import deque

def solution(arr) :
    matrix_lst = deque([np.array(arr)])
    zero_cnt, one_cnt = 0, 0
    
    while len(matrix_lst) > 0 :
        check = matrix_lst.popleft()
        # 모두 1인지 확인
        if check.sum() == len(check)**2 :
            one_cnt += 1
        # 모두 0인지 확인
        elif check.sum() == 0 :
            zero_cnt += 1
        # 둘다 아니면 구간 분할
        else :
            l = len(check)
            if l == 1 :
                if check.sum() == 0 :
                    zero_cnt += 1
                else :
                    one_cnt += 1
            else :
                top_left, top_right = check[:l//2, :l//2], check[:l//2 , l//2:]
                botton_left, bottom_right = check[l//2:, :l//2], check[l//2:, l//2:]
                matrix_lst.extend([top_left, top_right, botton_left, bottom_right])
    return [zero_cnt, one_cnt]

👩‍🏫 아이디어

1. 메모리와 복잡도의 Trade-Off

• 저는 문제를 접근할 때 대부분에 문제에서 "메모리와 문제 난이도의 복잡도가 trade off 관계가 있다"고 생각하고 접근합니다.
• 또한 문제를 접근할 때 패턴을 찾는데, 구조상으로는 (1) 초기 위치로의 이동, (2) 초기 위치에서의 조건확인 이 두가지를 큰 틀으로 접근합니다.
• 이번 문제는 (1)과 (2) 모두 2차원의 접근 방식이 필요하여 복잡도가 높은 문제라고 생각했습니다.
• 따라서, 문제의 복잡도를 낮추기 위해 메모리를 사용하여 "정보"를 저장시켜야 한다고 생각했습니다.
• 정보는, 초기 위치와 탐색해야 할 Matrix가 후보군 이었으나,탐색해야 할 Matrix를 정보로 저장시키는게 문제를 더 직관적이고 간결하게 풀 수 있을 것 같았습니다.

2. 프랙탈 구조

• 문제를 보고 프랙탈이 생각났습니다. 2차원 프랙탈 구조를 어떻게 컴퓨터에게 인식시킬까 고민하면서 풀었습니다.

프로그래머스 : 124 나라의 숫자

🤡124 나라의 숫자(Lv.2)

🤑풀이

def solution(n) :
    l, sum_l, m = 0, 0, n
    # l : 자리수, m : 구한 자리수(l)에서 몇 번 째 숫자인지
    while True :
        l += 1
        sum_l += 3**l
        m -= 3**l
        if sum_l >= n :
            break
    m = m-1
    num_lst = ""
    hash = {0 : '1', 1 : '2', 2 : "4"}
    for i in list(range(l)) :
        m, mod = divmod(m, 3)
        num_lst += hash[mod]
    return num_lst[::-1]
        

👩‍🏫 아이디어

1. 나열 후 패턴 찾기

• 저는 문제를 접근할 때 직관적으로 아이디어가 떠오르지 않으면 문제에서 주어진 조건대로 나열해서 패턴을 찾으려고 하고 있습니다.
• 처음에는 3진법, 4진법으로 변환해서 풀면 되겠다고 생각했는데 그렇지 않았습니다. 그래서 수를 나열해서 패턴을 찾아서 문제를 해결했습니다.
• 이런 문제는 종종 보이는 것 같아서 풀이를 좀 적어보려고 합니다.

(1) : 자리수 찾기

(2) : 각 자리수의 숫자 찾기

(3) : 문제의 조건대로 변환하기