[Coding Test] 프로그래머스 - 비밀지도

[문제설명]

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

 

지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다.

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

지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다.

암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다. 네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

 

 

---

문제 !

1) 라이브러리 도움없이 2개 배열의 값을 2진수로 변환시키는데 시간이 많이 소요됨.

2) 2진수로 변환했을 때, n의 길이만큼 0을 채워넣는 것이 어려움 (n=5, 3(10진수) ->'00011'(2진수))

idea!

2진수로 변환하지 않고, 바로 '#', ' '표시하기

1) n이 주어질 때 배열에 들어갈 수 있는 숫자는 최대 2**n-1까지이다.

- 가령, n=5일 때 2진수는 최대 5칸 안에 표기되어야 하므로 최대 숫자는 11111(2*4+2*3+2*2+2*1+2*0), 10진수로는 2**5-1인  31까지 나올 수 있다. 

2) 2진수를 표기한 박스에 패턴

홀수인 9는 2의 거듭제곱 2**3(=8)+2**1(=1) 으로 나타나타낼 수 있다. 마찬가지로, 20과 28도 아래와 같이 표기 가능하다.

20 = 2**4(=16)+2**2(=4)

28 = 2**4(=16)+2**3(=8)+2**2(=4)

위의 과정에서 2**n-1 보다 작은 10진수를 2**(n-1)에서 n을 한 차수씩 줄이면서 비교하는 방법을 생각해냈다.

 

-------------------------------  예 시 -------------------------------

28, n=5

28이 2**4보다 크거나 같으므로 28-2**4 = 12 ---- 1st칸 '#'

12가 2**3보다 크거나 같으므로 12-2**3 = 4 ---- 2nd칸 '#'

4가  2**2보다 크거나 같으므로 4-2**2 = 0 ---- 3rd칸 '#'

0이  2**1보다 크거나 같지 않으므로 연산 없음 ---- 4th칸 ' '

0이  2**0보다 크거나 같지 않으므로 연산 없음 ---- 5th칸 ' '

>> '###  '

 

9, n=5

9가 2**4보다 크거나 같지 않으므로 연산 없음---- 1st칸 ' '

9가 2**3보다 크거나 같으므로 9-2**3 = 1 ---- 2nd칸 '#'

1이  2**2보다 크거나 같지 않으므로 연산 없음---- 3rd칸 ' '

1이  2**1보다 크거나 같지 않으므로 연산 없음 ---- 4th칸 ' '

9가 2**3보다 크거나 같으므로 9-2**0 = 0 ---- 5th칸 '#'

>> ' #  #'
-----------------------------------------------------------------------

def solution(n, arr1, arr2):
    answer = []
    for i in range(len(arr1)):
        temp = ''
        for j in range(n):
        ## arr1이 숫자가 2**(n-1)보다 큰지 비교 >> 크다면 2**(n-1)만큼 빼기
            if arr1[i] >= (2**(n-1-j)):
                arr1[i] -= (2**(n-1-j))
                temp += "#"
                ## arr2이 숫자도 2**(n-1)와 비교, arr1에서 이미 '#'표기 했다면 그냥 넘어감.
                if arr2[i] >= (2**(n-1-j)):
                    arr2[i] -= (2**(n-1-j))
            else:	## arr1에서 '#'표기 없다면 arr2가 해당되는지 확인.
                if arr2[i] >= (2**(n-1-j)):
                    arr2[i] -= (2**(n-1-j))
                    temp += "#"
                
                else:
                    temp += (" ")
        answer.append(temp)
    return answer

방법이 간단하다보니 아이디어 도출하고 나서 금방 코드로 옮길 수 있었다.

기존과 조금 다르게 2진수 변환하는 방법을 고안하는 과정이 재미있었다.