프로그래머스 공부/Python

[Level 1 / Python] 비밀지도(2018 KAKAO BLIND RECRUITMENT)

#자유의날개 2020. 11. 12. 00:38
반응형

문제 설명

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

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

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

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

  4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

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

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

  • 1 ≦ n ≦ 16

  • arr1, arr2는 길이 n인 정수 배열로 주어진다.

  • 정수 배열의 각 원소

     x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출처 : programmers.co.kr/learn/courses/30/lessons/17681

풀이 방법

아래와 같이 세가지 문제로 나누어 접근했다.

  1. 십진수를 이진수로 변경

  2. 위의 방법을 이용해 arr1 배열과 arr2 배열을 이진수 값을 가진 배열들로 변경

  3. arr1 배열과 arr2 배열의 결합

먼저 입력된 십진수를 이진수로 변경하기 위해 전에 풀었었던 "3진법 뒤집기"를 활용하여 이진수로 만드는 함수를 만들었다. 입력된 한 변 크기 n 값을 고려하기 위해 이진수로 변경 후 길이가 n이 아닐 경우 앞에 0을 채워주고, 이진수가 뒤집어져서 만들어지기 때문에 [::-1]을 사용하여 이진수를 만들었다.

1
2
3
4
5
6
7
8
9
10
11
def binary(n, value):
    binary = ''
    for i in range(n):
        while value > 0:
            binary += str(value % 2)
            value = int(value / 2)
        if len(binary) == n:
            return binary[::-1]
        else:
            binary += str(0*(n-len(binary)))
    return binary[::-1]
 cs

다음으로 arr1 배열과 arr2 배열을 이진수 값을 가진 배열들로 변경하기 위해 zip 함수와 위에서 만든 binary 함수를 사용했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
arr1 = [46, 33, 33 ,22, 31, 50]
arr2 = [27 ,56, 19, 14, 14, 10]
n = 6
 
binary_arr1 = []
binary_arr2 = []
for i, j in zip(arr1, arr2):
    binary_arr1.append(binary(n, i))
    binary_arr2.append(binary(n, j))
 
print(binary_arr1)
print(binary_arr2)
 
"""
['101110', '100001', '100001', '010110', '011111', '110010']
['011011', '111000', '010011', '001110', '001110', '001010']
"""
 cs

마지막으로 변경된 arr1 배열과 arr2 배열을 합치기 위해 몇 가지 트릭을 사용했다. 예를 들면 '101110'과 '011011'을 결합하기 위해 문자열을 숫자로 바꾸고 더하게 되면 112121이 되는데 여기서 2를 다시 1로 변경하면 111111이 되어 문제에서 원하는 결과를 도출할 수 있다. 만약 앞자리가 둘 다 0인 경우는 int로 타입을 변경하여 덧셈을 할 수 없으므로 모든 문자열에 먼저 '1'을 앞부분에 붙여주고 모든 연산이 끝난 뒤 슬라이스를 사용해 앞부분을 없앴다. 그리고 마지막으로 '1'은 '#'으로 '0'은 ' '으로 변경해주어 문제를 해결했다.

1
2
3
4
5
6
7
8
9
result = []
for i, j in zip(binary_arr1, binary_arr2):
    result.append(str(int('1' + i)+int('1' + j)).replace('2', '1').replace('1', '#').replace('0', ' '))
 
print(result)
 
"""
['######', '###  #', '##  ##', ' #### ', ' #####', '### # ']
"""
 cs

소스 코드

전체 코드는 아래와 같다. 다른 사람의 풀이를 보니 정수를 이진수로 변환하는 bin() 함수와 문자열의 길이를 확인 후 공백을 채워주는 rjust() 함수를 사용하여 매우 간결하게 풀 수 있다는 것을 알았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, arr1, arr2):
    answer = []
    binary_arr1 = []
    binary_arr2 = []
    for i, j in zip(arr1, arr2):
        binary_arr1.append(binary(n, i))
        binary_arr2.append(binary(n, j))
    for i, j in zip(binary_arr1, binary_arr2):
        answer.append(str(int('1' + i)+int('1' + j)).replace('2', '1').replace('1', '#').replace('0', ' ')[1:])
    return answer
 
def binary(n, value):
    binary = ''
    for i in range(n):
        while value > 0:
            binary += str(value % 2)
            value = int(value / 2)
        if len(binary) == n:
            return binary[::-1]
        else:
            binary += str(0*(n-len(binary)))
    return binary[::-1]
 cs

 

반응형