다메카솔

문제

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

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

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

발상

주어진 수를 2진수로 변환한 뒤에 or 연산을 하여 0과 1을 주어진 조건에 맞게 변환하는 문제이다.

이진수변환을 하면서 자리수가 다른 부분이나 형변환 같은 이슈를 처리하는 부분이 핵심이었다.

의사코드

1. 주어진 배열 이진수 변환
2. 반복문{
	1. 변환된 이진수 비교
    	1. 둘 다 0이면 0
        2. 아니면 #
}
3. 완성된 배열 반환

개선

주어진 배열을 따로따로 이진수 변환하고, 자리수 맞추고, 그 뒤에 변환하느라 고생하였다.

처음에는 Integer클래스의 toBinaryString으로 문자열로 바꾸고, 다시 숫자 세서 String클래스로 포매팅하고, 거기서 다시 문자를 추출해서 비교하였는데 케이스가 많아지니까 타임아웃이 발생하였다.

최적화를 위해 고민하여서 통과하긴 하였는데, 다른 사람들의 풀이를 보니 처음에 주어진 숫자값을 따로 가공하지 않고 바로 비트연산을 통해 원하는 값을 얻어서 많은 절차를 생략하였다.

데이터는 모두 0과 1의 조합으로 되어있다는 사실을 잊지 말고 비트단위 연산도 항상 염두에 두도록 하자.