Home PS) 비밀지도
Post
Cancel

PS) 비밀지도

Posted Sep 10, 2023
7 min read

출처
: Programmers

문제

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

  1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 “공백”(“ “) 또는 “벽”(“#”) 두 종류로 이루어져 있다.
  2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 “지도 1”과 “지도 2”라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
  3. “지도 1”과 “지도 2”는 각각 정수 배열로 암호화되어 있다.
  4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

나의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

def solution(n, arr1, arr2):
    
    res_arr1 = []
    res_arr2 = []
    for i in range(n):
        bin_arr1 = loop_divide_by_2(arr1[i], n)
        bin_arr2 = loop_divide_by_2(arr2[i], n)
        # print("bin_arr1\n==>", bin_arr1)
        # print("bin_arr2\n==>", bin_arr2)

        bin_to_sharp(bin_arr1)
        bin_to_sharp(bin_arr2)
        res_arr1.append(bin_arr1)
        res_arr2.append(bin_arr2)
    # print("this is arr1\n==>", res_arr1)
    # print("this is arr2\n==>", res_arr2)

    answer = merge_two_arrs(res_arr1, res_arr2)
    print(answer)
    return answer

""" 
인자 값을 2진수로 변환
"""
def loop_divide_by_2(n, length):
    
    temp_arr = [-1 for _ in range(length)]
    quot = n
    cnt = length - 1

    """ 
    정지조건
     : quot <= 1이 될때
    """
    while (True):
        mod = quot % 2
        quot = int(quot / 2)
        
        """         
        mod(0 또는 1) 값을 
        cnt번째에 갱신 입력
        """
        temp_arr[cnt] = mod
        cnt -= 1
        
        if (quot == 0 or quot == 1):
            temp_arr[cnt] = quot
            break
        
    # print("current quot value is\n=>", quot)
    # print("converted binary number is\n=>", temp_arr)
    return temp_arr

""" 
2진수 배열 --> "#"과 " "의 문자열로
"""
def bin_to_sharp(bin_arr):
    convert = ""
    for i in range(len(bin_arr)):
        temp_val = bin_arr[i]
        if (temp_val == 0):
            convert += chr(32)
        elif (temp_val == 1):
            convert += '#'
        else:
            pass
    # print("converted string is\n=>" + ' ' + '[' + convert + ']')

def merge_two_arrs(arr1, arr2):
    sharp_char = '#'
    blank_char = chr(32)
    size = len(arr1)
    merged = ['' for _ in range(size)]
    for i in range(size):
        str_temp_mrg = ""
        for j in range(size):
            temp_1 = arr1[i][j]
            temp_2 = arr2[i][j]
            if (temp_1 == 1 or temp_2 == 1):
                str_temp_mrg += sharp_char
            elif ((temp_1 == -1 or temp_1 == 0) and (temp_2 == -1 or temp_2 == 0)):
                str_temp_mrg += blank_char
        merged[i] = str_temp_mrg

    # print("merged arr is\n==>", merged)

    # for a in range(size):
    #     for b in range(size):
    #         print(merged[a][b], end='')
    #     print('', end='\n')
    # print(merged)
    return merged


다른 사람들의 풀이

1
2
3
4
5
6
7
8
9

def solution(n, arr1, arr2):
    answer = []
    for i,j in zip(arr1,arr2):
        a12 = str(bin(i|j)[2:])
        a12=a12.rjust(n,'0')
        a12=a12.replace('1','#')
        a12=a12.replace('0',' ')
        answer.append(a12)
    return answer

정말 아름답게 짧은 풀이이다…
공부겸 저기에 나오는 코드 하나하나 뜯어보면 이렇다.

zip() 함수

우선 zip() 함수는
여러 개의 순회가능한iterable 데이터를
병렬적으로in parallel 순회iterate한다.
이때, 각 데이터로부터 하나씩 뽑아서
하나의 튜플로 만들어 순회한다.
(출처: 파이썬 공식문서 中 내장함수 부분)

즉, for i, j in zip(arr1, arr2)은 이런 식이다.

1
2
3
4

arr1 = [9, 20, 28, 18, 11]
arr2 = [30, 1, 21, 17, 28]
for i, j in zip(arr1, arr2):
   print(i, j) 

1
2
3
4
5

9 30
20 1
28 21
18 17
11 28


bin() 함수

그 다음으로, bin() 함수는 이진수로 변환한다.
이때, 주의해야 할 점은

1

bin(16)

1

'0b10000'

이렇게 '0b'라는 문자가 붙어서 나온다는 것이다.
그래서 위의 풀이를 잘 보면,

1

bin(i|j)[2:]

2번 원소부터 마지막 원소까지만을 참조한다.

rjust() 함수

그 다음으로, rjust() 함수이다.

1

str.rjust(width[, fillchar])

인자는 이런 식으로 되어있는데,
fillchar는 채우고자 하는 문자이고,
width는 반환되는 문자열의 최종길이이다.

즉, 이런 식이다.

1
2
3
4
5
6
7

print(str1.rjust(len(str1), 'x')) 
print(str1.rjust(len(str1) + 1, 'x')) 
print(str1.rjust(len(str1) + 2, 'x')) 

00111
x00111
xx00111

위의 풀이 코드에서는
상대적으로 크기가 작은 값이 이진수로 변환될 때
각 이진수의 길이가 서로 다른 경우를 위해 쓰였다.
일종의 패딩 값인 것이다.

코드 하나하나를 놓고 보면,
(rjust를 제외한다면)
거의 다 알고 있고 일반적인 것들이다.

두 개의 배열(arr1, arr2) 중에서
'#'이 하나만 있어도 결과에 '#'이 나오므로
이러한 점을 |(or) 연산으로 잘 연결시킨 풀이인 것 같다.

PS
Python PS Programmers
Contents