프로그래머스

프로그래머스 비밀지도 풀이: 비트 OR와 고정 길이 이진수

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 비밀지도
  • 출처: 프로그래머스, 2018 KAKAO BLIND RECRUITMENT
  • 자체 판단 난이도: Level 2

각 숫자를 이진수로 바꾼 뒤 두 지도의 같은 위치를 비교해야 한다. 두 숫자를 더하는 것이 아니라, 같은 자리의 비트 중 하나라도 1이면 1로 만드는 비트 OR를 사용해야 한다. 그 후 이진수를 정확히 n자리로 맞추고 1과 0을 벽과 공백으로 바꿔야 한다. 반복문 자체는 간단하지만 비트 OR와 고정 길이 이진수 표현을 함께 이해해야 하므로 Level 2로 판단했다.

1. 문제 요약

크기가 n x n인 두 개의 지도가 숫자 배열 arr1, arr2로 주어진다. 각 숫자는 한 행의 벽 위치를 이진수로 나타낸다.

  • 이진수의 1은 벽(#)이다.
  • 이진수의 0은 빈 공간( )이다.
  • 두 지도 중 하나라도 벽이면 최종 지도에서도 벽이다.
  • 최종 지도는 각 행의 길이가 정확히 n인 문자열 배열로 반환한다.
  • n은 1 이상 16 이하다.
  • 배열의 각 값은 0 이상 2^n - 1 이하다.

예를 들어 n = 5이고 한 행의 값이 9라면 이진수 01001로 표현한다. 앞의 0도 행의 길이를 맞추기 위해 반드시 포함해야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

상태 전이와 경계 처리

같은 행의 두 숫자를 비트 단위 OR 연산(|)으로 합친다. OR 연산은 각 비트에서 다음과 같이 동작한다.

0 | 0 = 0  -> 공백
0 | 1 = 1  -> 벽
1 | 0 = 1  -> 벽
1 | 1 = 1  -> 벽

합친 숫자를 n자리 이진수 문자열로 바꾼 뒤, 1은 #, 0은 공백으로 치환한다. Python의 format(value, f"0{n}b")를 사용하면 값이 작아도 왼쪽에 0을 채워 항상 길이 n인 문자열을 만들 수 있다.

비트 OR와 고정 폭 변환의 역할

두 지도의 같은 칸 중 하나라도 벽이면 최종 결과가 벽이다. 이는 두 숫자를 이진수로 보았을 때 같은 자리의 비트 중 하나라도 1이면 1로 만드는 OR 연산과 정확히 같다.

따라서 각 행에서 복잡하게 두 문자열을 비교하거나 별도의 2차원 배열을 만들 필요 없이, arr1[row] | arr2[row] 하나로 해당 행의 벽 위치를 합칠 수 있다.

행 변환과 고정 길이 처리

예를 들어 n = 5, value = 9이면 일반적인 이진수 문자열은 "1001"이지만 지도 행에는 다섯 칸이 필요하므로 "01001"이어야 한다.

value = 9
format(value, "05b") = "01001"
"1" -> "#", "0" -> " "
결과 = " #  #"

이진수 변환에서 앞의 0을 생략하면 행 길이가 짧아지고 벽의 위치가 왼쪽으로 밀린 것처럼 보일 수 있다. 반드시 n을 폭으로 지정해야 한다.

오답 접근과 반례

두 지도의 숫자를 더한 뒤 이진수로 바꾸면 OR 연산과 같은 결과가 항상 나오지 않는다.

n = 4
arr1의 행 = 3  -> 0011
arr2의 행 = 1  -> 0001

이 경우 OR 결과는 0011이지만, 숫자를 더해도 4가 되어 0100으로 바뀐다. 같은 칸에 벽이 하나라도 있는지를 표현해야 하므로 덧셈이 아니라 비트 OR를 사용해야 한다.

또한 bin(value)[2:]만 사용하면 앞의 0이 사라진다. n = 4, value = 1은 0001이어야 하지만 bin(1)[2:]는 "1"이므로 zfill(n) 또는 폭을 지정한 format이 필요하다.

시간·공간 복잡도

행 n개를 한 번씩 처리하고 각 행의 길이는 최대 n이므로 시간 복잡도는 O(n^2)이다. 결과 문자열 배열을 제외하면 현재 행의 숫자와 변환 문자열만 사용하므로 추가 공간 복잡도는 출력 크기를 제외할 때 O(n)이다. 반환 결과까지 포함하면 공간 복잡도는 O(n^2)이다.

3. 문제 해결 코드 (Python)

각 행의 숫자를 OR로 합친 뒤 n자리 이진수로 포맷한다. 이후 문자열의 1과 0을 각각 벽과 공백으로 바꿔 결과 목록에 추가한다.

def solution(n, arr1, arr2):
    answer = []

    for left, right in zip(arr1, arr2):
        merged = left | right
        row = format(merged, f"0{n}b")
        answer.append(row.replace("1", "#").replace("0", " "))

    return answer

format(merged, f"0{n}b")에서 b는 이진수, 0{n}은 왼쪽을 0으로 채워 폭을 n으로 맞추라는 의미다. replace를 적용할 때 먼저 1을 #으로 바꾸고 0을 공백으로 바꾸면, 모든 비트가 문제에서 요구하는 지도 문자로 변환된다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 비트 OR 결합과 앞자리 0 채우기를 확인할 수 있다.

assert solution(5, [9, 20, 28, 18, 11], [30, 1, 21, 17, 28]) == [
    "#####", "# # #", "### #", "#  ##", "#####"
]
assert solution(1, [0], [0]) == [" "]

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 앞의 0, OR 연산, 최소 크기 지도를 확인했다. 출력에 포함된 공백은 행 길이를 맞추기 위해 의도적으로 들어간 문자다.

공식 예제

입력: n = 5
arr1 = [9, 20, 28, 18, 11]
arr2 = [30, 1, 21, 17, 28]

기대 출력:
["#####", "# # #", "### #", "#  ##", "#####"]
확인 결과: 통과
입력: n = 6
arr1 = [46, 33, 33, 22, 31, 50]
arr2 = [27, 56, 19, 14, 14, 10]

기대 출력:
["######", "###  #", "##  ##", " #### ", " #####", "### # "]
확인 결과: 통과

추가 검증 1: 최소 크기에서 빈 공간

입력: n = 1, arr1 = [0], arr2 = [0]
기대 출력: [" "]
확인 결과: 통과
검증 목적: 두 비트가 모두 0일 때 한 칸의 공백을 반환하는지 확인

추가 검증 2: 최소 크기에서 벽

입력: n = 1, arr1 = [1], arr2 = [0]
기대 출력: ["#"]
확인 결과: 통과
검증 목적: 두 지도 중 하나만 벽이어도 최종 칸이 벽인지 확인

추가 검증 3: 앞의 0이 필요한 행

입력: n = 4, arr1 = [1, 2, 4, 8], arr2 = [0, 0, 0, 0]
기대 출력: ["   #", "  # ", " #  ", "#   "]
확인 결과: 통과
검증 목적: 이진수의 앞쪽 0을 유지해 벽 위치를 정확히 표현하는지 확인

5. 다른 풀이 방식 검색 및 비교

각 행을 이진수 문자열로 바꾼 뒤 같은 위치의 문자를 직접 비교하는 방법도 가능하다. 이 글의 방식은 두 숫자를 먼저 OR로 합쳐 벽 위치를 계산하므로, 같은 칸에 벽이 있는지에 대한 조건을 비트 연산 하나로 표현한다.

bin(value)[2:].zfill(n)으로 이진수와 앞의 0을 직접 처리할 수도 있다. format은 폭과 진법을 한 번에 지정할 수 있어 같은 결과를 더 간결하게 표현한다.

마무리

비밀지도는 두 숫자의 같은 비트 중 하나라도 1이면 벽이라는 조건을 비트 OR로 옮기는 문제다. 각 행을 arr1[i] | arr2[i]로 합친 뒤 n자리 이진수로 변환하고, 1과 0을 #과 공백으로 바꾸면 된다. 이진수 앞의 0을 유지하는 고정 폭 변환이 결과를 정확히 만드는 핵심이다.

#비트마스크#프로그래머스#난이도 2