2018 KAKAO BLIND RECRUITMENT에 나온 비밀지도 문제입니다.
문제
비밀지도
네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.
지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ") 또는벽("#") 두 종류로 이루어져 있다.
전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다.
암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.
네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.
https://programmers.co.kr/learn/courses/30/lessons/17681
문제 해설
지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
문제에서 답을 알려주고 있다. 지도 1과 2중 하나라도 벽인 부분은 벽이고 지도 1과 지도 2에서 모두 공백인 부분은 전체지도에서도 공백이란 의미는 두 지도를 OR 하게 되면 비밀지도를 얻을 수 있다는 소리다. 비트 연산을 조금이라도 이해하고 있다면 아주 쉽게 풀 수 있다.
def solution(n, arr1, arr2):
answer = []
for i in range(n):
line = arr1[i] | arr2[i]
temp = ""
for j in range(n):
if line - 2 ** (n - j - 1) >= 0:
line -= 2 ** (n - j - 1)
temp += "#"
else:
temp += " "
answer.append(temp)
return answerarr1[i]와 arr2[i]를 OR연산하게 되면 해당 라인의 벽과 공백을 나타내는 10진수의 숫자를 얻을 수 있다. 이 숫자를 이용해 비밀지도의 벽과 공백을 표현한다.
10진수의 숫자를 2진수로 표현하는 방법은 여러 방법이 있겠지만 (2^(n-1)) 부터 지수가 0이 될때까지 뺄 수 있으면 빼고 1, 뺄 수 없으면 0으로 표현하는 방법을 이용했다.
간단한 문제인 만큼 가장 많은 사람이 풀었던 문제이다.
