문제

비트 연산자를 사용하는 문제

1. n - 지도의 크기 (1 <= n <= 16)

2. arr1, arr2 - 길이 n인 배열

3. 정수 배열의 원소의 크기 (0<= x <= 2^n - 1)
   (참고로, 정수 최대 크기는 2^31 - 1 == 2147483647 == 약 20억)

4. "#" - 벽, " " - 공백

5. 전체 지도 규칙
   arr1, arr2 두 지도에 대해서

• 둘 중 하나에서 벽이면 전체지도에서 벽
• 모두 공백이면 전체지도에서 공백

전체 지도를 구하세요.

문제 링크

---

1. 첫인상

문제를 보면 비트 연산자를 쓰라는 인상을 정말 강하게 줍니다.

나중에 해설도 읽어보니, 비트 연산자를 사용할 줄 아는지 물어보는 문제였고, 사실 문자열로 쪼개는것 보다 그게 더 편합니다.

혹시, 나는 비전공자여서 이런거 몰라 보다. 이번에 알지 뭐 ㅋ

2. 접근 과정

1) 문제 쪼개기

문제를 작게 쪼개면 다음과 같습니다.

1. 두개의 지도 입력

2. 두개의 지도에서 n번째 숫자 읽기

3. 2번에서 읽은 n번째 숫자에 대해 다음 규칙 적용하기

• 둘 중 하나에서 벽이면 전체지도에서 벽
• 모두 공백이면 전체지도에서 공백

4. 결과 만들기

1번, 4번은 일반적인 읽기, 쓰기 이기 때문에 2, 3번을 집중적으로 봅시다.

3. 두개의 지도에서 n번째 숫자 읽기

10진수를 2진수로 바꿔서 문자열로 바꿔서 읽는 생각은 잠시 접어두고 비트에 대해 알아봅시다.

1) 쉬프트 연산

프로그래밍에는 쉬프트 연산자가 있습니다. (무슨 개발을 하느냐에 따라 처음 볼수도 있습니다.)

비트를 주어진 수만큼 왼쪽으로 밀어줍니다.

1 << 3 은 1을 왼쪽으로 3칸 민다는 의미이고, 그렇게 되면 8이 됩니다.

2^n 으로 생각하면 편합니다.

2) 비트 연산자

bitwise operator, 비트 단위 연산이라고 부릅니다.

혹시 && 과 &, || 과 | 의 차이를 아시나요?

2개는 논리 연산자
1개는 비트 연산자 입니다.

그래서 왜 필요하나면, 문제에서 2개의 비트 연산자가 필요합니다.

• & 연산자
  arr1, arr2의 정수 숫자에 대해 n번째 비트가 1인지 0인지 검사

• | 연산자
  arr1, arr2 정수 숫자의 n번째 비트가 모두 0인지, 혹은 1을 한개 이상 포함하고 있는지 검사

3) & 연산자

& 연산의 결과는 둘다 1일 때만 1인, 나머지는 0입니다.

이를 이용해 n번째 비트가 1인지 확인할 수 있습니다.

주의할점은 결과가
n번째 비트가 1이면 0이 아닌 수
n번째 비트가 0이면 0입니다.

예) 9 & (1 << n)

arr1의 n번째 비트가 1인지 확인하는 방법은 다음과 같습니다.

for(int j=n-1; j>=0; j--){
    if(arr1[i] & (1 << j)) {
      // n번째 비트가 1
    }
    else{
      // n번째 비트가 0
      // if문에서 조건이 0이면 false로 인식합니다.
    }
}

4) | 연산자

사실 문제의 다음 내용은 or 연산을 의미합니다.
(모두 0일때만 0, 1이 하나라도 있으면 1)

• 둘 중 하나에서 벽이면 전체지도에서 벽
• 모두 공백이면 전체지도에서 공백

이를 3번의 & 연산자와 결합시키면 코드는 다음과 같습니다.

// 배열 요소의 최대 크기는 2^n - 1, 최대 n개의 비트를 가지고 있습니다.
for(int j=n-1; j>=0; j--){

    // 1. arr1, arr2의 n 번째 비트가 하나라도 1인 경우
    if((arr1[i] & (1 << j)) | (arr2[i] & (1 << j))){
        num += "#";
    }
    // 2. arr1, arr2의 n 번째 비트가 모두 0인 경우
    // (if문의 조건에 0이 들어오면 false로 인식합니다.)
    else{
        num += " ";
    }
}

4. 시간 복잡도 계산

2중 for문 비트 연산 = O(n^2) O(1) = O(n^2)
n의 최대값이 16이기 때문에 O(256)

1억에 1초 걸리기 때문에 시간안에 충분히 풀 수 있습니다.

5.코드

1) C++

#include <string>
#include <vector>

using namespace std;

/*
    시간 복잡도: O(n^2)
    공간 복잡도: O(n)
    사용한 알고리즘: 쉬프트 연산
    사용한 자료구조: 배열
*/


vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;

    // n개의 숫자에 대해 n번 반복합니다.
    for(int i=0; i<n; i++){
        // 결과를 문자열로 저장할 변수 num
        string num = "";

        // 배열 요소의 최대 크기는 2^n - 1, 최대 n개의 비트를 가지고 있습니다.
        for(int j=n-1; j>=0; j--){

            // 1. arr1, arr2의 n 번째 비트가 하나라도 1인 경우
            if((arr1[i] & (1 << j)) | (arr2[i] & (1 << j))){
                num += "#";
            }
            // 2. arr1, arr2의 n 번째 비트가 모두 0인 경우
            // (if문의 조건에 0이 들어오면 false로 인식합니다.)
            else{
                num += " ";
            }
        }
        answer.push_back(num);
    }

    return answer;
}

2) java

/*
    시간 복잡도: O(n^2)
    공간 복잡도: O(n)
    사용한 알고리즘: 쉬프트 연산
    사용한 자료구조: 배열
*/

class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
      String[] answer = {};
      
      answer = new String[n];
      
    // n개의 숫자에 대해 n번 반복합니다.
    for(int i=0; i<n; i++){
        // 결과를 문자열로 저장할 변수 num
        String num = "";

        // 배열 요소의 최대 크기는 2^n - 1, 최대 n개의 비트를 가지고 있습니다.
        for(int j=n-1; j>=0; j--){

            // 1. arr1, arr2의 n 번째 비트가 하나라도 1인 경우
            if(((arr1[i] & (1 << j)) | (arr2[i] & (1 << j))) != 0){
                num += "#";
            }
            // 2. arr1, arr2의 n 번째 비트가 모두 0인 경우
            // (if문의 조건에 0이 들어오면 false로 인식합니다.)
            else{
                num += " ";
            }
        }
        answer[i] = num;
    }      
      return answer;
  }
}

3) python3

'''
    시간 복잡도: O(n^2)
    공간 복잡도: O(n)
    사용한 알고리즘: 쉬프트 연산
    사용한 자료구조: 배열
'''

def solution(n, arr1, arr2):
    answer = []
    
    for i in range(n):
        num = ""
        for j in reversed(range(n)):
            
            if arr1[i] & (1 << j) | arr2[i] & (1 << j):
                num += "#"
            else:
                num += " "
        answer.append(num)
    
    return answer

4) javascript

/*
    시간 복잡도: O(n^2)
    공간 복잡도: O(n)
    사용한 알고리즘: 쉬프트 연산
    사용한 자료구조: 배열
*/

function solution(n, arr1, arr2) {
    var answer = [];
    
    // n개의 숫자에 대해 n번 반복합니다.
    for(let i=0; i<n; i++){
        // 결과를 문자열로 저장할 변수 num
        let num = "";

        // 배열 요소의 최대 크기는 2^n - 1, 최대 n개의 비트를 가지고 있습니다.
        for(let j=n-1; j>=0; j--){

            // 1. arr1, arr2의 n 번째 비트가 하나라도 1인 경우
            if((arr1[i] & (1 << j)) | (arr2[i] & (1 << j))){
                num += "#";
            }
            // 2. arr1, arr2의 n 번째 비트가 모두 0인 경우
            // (if문의 조건에 0이 들어오면 false로 인식합니다.)
            else{
                num += " ";
            }
        }
        answer.push(num);
    }    
    
    return answer;
}