[Programmers] Level 1 - [1차] 비밀지도

문제 링크
https://programmers.co.kr/learn/courses/30/lessons/17681

어떻게 풀었나?

1. arr1 과 arr2 의 10진수 → 2진수 변환

def binary(n, bin_len):
    n_binary = deque()
    while 1:
        a, b = divmod(n, 2)
        n_binary.appendleft(b)
        n = a
        if a == 0:
            break
    while len(n_binary)!=bin_len:
        n_binary.appendleft(0)
    return n_binary

💡 Python에서 몫과 나머지 구하는 방법

a, b = divmod(n, 2)

a : n을 2로 나누었을 때 몫
b : n을 2로 나누었을 때 나머지

하지만 재귀함수를 사용하여 2진수 변환을 할 수 있다.
위에서 반복되는 과정은

1. n을 2로 나누고 나머지를 저장한다.
2. 몫을 2로 나눈다.

그렇다면 재귀함수의 탈출 조건은 무엇이냐?

• 몫이 0이 될 경우

따라서 재귀함수를 사용하여 2진수 변환하는 함수는 아래와 같이 작성할 수 있다.

def binary(n, bin_len, bin_arr):
    a, b = divmod(n, 2)
    bin_arr.appendleft(b)
    if a==0:
        while len(bin_arr)!=bin_len:
            bin_arr.appendleft(0)
        return bin_arr
    else:
        return binary(a, bin_len, bin_arr)

💭 재귀함수 사용하는 것 vs 사용 안하는 것 속도 차이?

재귀함수 사용하지 않은 경우가 더 빠르다. 왜?

2. 비밀지도 해독하기

        decoded = ""
        for b1, b2 in zip(binary1, binary2):
            if b1+b2>=1:    
                decoded+= "#"
            else:
                decoded+= " "
        answer.append(decoded)

문제 설명에서 비밀지도 해독하는 방법은 아래와 같다.

전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.

따라서 b1+b2>=1 가 참인 경우는 b1 와 b2 둘 중 무조건 하나는 벽이라는 의미이므로, 전체 지도에서도 벽이다.

💭 코드 개선해볼 수 있을까?

1. 비밀지도 해독 문자열 합치기 방법 개선

문자열을 합치는 방법에는 두 가지가 있다.
1. 문자열을 더해나가는 방법
2. list에 넣은 다음, string.join()을 통해 마지막에 처리하는 방법

내가 기존에 사용한 방법은 첫 번째, 문자열을 더해나가는 방법이었다.

기존 비밀지도 해독 문자열 배열을 만드는 과정은 아래와 같다.

decoded = ""
for b1,b2 in zip(binary1, binary2):
	if b1+b2>=1:     
		decoded+="#
	else:
		decoded+=" "
answer.append(decoded)

Python에서 문자열은 immutable한 객체(object)으로, 요솟값을 변경할 수 없다.
따라서 새로운 문자를 더하여 문자열을 생성할 경우, 기존 문자열에 더해지는 것이 아니라 새로운 문자열 객체가 생성되는 것이다. 이때 deep copy가 일어나고, 특정 부분만 다른 새로운 문자열 객체를 만들게 된다.

하지만 list는 mutable한 객체로, 요솟값을 변경할 수 있다. 이로 인해 일반적으로 특정 부분을 치환하는 mutable 이 immutable보다 더 빠르다.

따라서 문자열이 아닌 list를 사용하여 비밀지도 해독 문자열 합치기 과정을 수행하도록 바꾸었다.

decoded = []
for b1,b2 in zip(binary1, binary2):
	if b1+b2>=1:     
		decoded.append("#")
	else:
		decoded.append(" ")
answer.append("".join(decoded))

💻최종 코드

from collections import deque

def binary(n, bin_len):
    n_binary = deque()
    while 1:
        a, b = divmod(n, 2)
        n_binary.appendleft(b)
        n = a
        if a == 0:
            break
    while len(n_binary)!=bin_len:
        n_binary.appendleft(0)
    return n_binary


def solution(n, arr1, arr2):
    answer = []
    
    for i in range(n):
        binary1, binary2 = binary(arr1[i],n), binary(arr2[i],n)
        decoded = []
        
        for b1, b2 in zip(binary1, binary2):
            if b1+b2>=1:    # 
                decoded.append("#")
            else:
                decoded.append(" ")
        answer.append("".join(decoded))
    
    return answer

참고 사이트

• Python 문자열 합치기 관련
  - https://brownbears.tistory.com/497
  - https://www.pymoon.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-%EB%AC%B8%EC%9E%90%EC%97%B4-%ED%95%A9%EC%B9%98%EA%B8%B0
  - https://wikidocs.net/91520
  - https://sweetlog.netlify.app/python/mutable_vs_immutable

• 2진수 변환 - 재귀함수 관련
  - https://minnit-develop.tistory.com/17
• 파이썬을 파이썬답게
  - https://programmers.co.kr/learn/courses/4008