[C++] level1 비밀지도 50067

📌비밀지도

📌풀이

이 문제는 카카오 해설에서도 다음과 같이 적혀있다.

이 문제는 비트 연산(Bitwise Operation)을 묻는 문제입니다. 이미 문제 예시에 2진수로 처리하는 힌트가 포함되어 있고, 둘 중 하나가 1일 경우에 벽 #이 생기기 때문에 OR로 처리하면 간단히 풀 수 있습니다. 아주 쉬운 문제였던 만큼 if else로 풀이한 분들도 많이 발견되었는데요. 정답으로는 간주되지만 이 문제는 비트 연산을 잘 다룰 수 있는지를 묻고자 하는 의도였던 만큼 앞으로 이런 유형의 문제를 풀 때는 비트 연산을 꼭 기억하시기 바랍니다. 이 문제의 정답률은 81.78%입니다.

문제에서 입출력 예시를 설명하면서 다음과 같은 사진을 보여준다.

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

이 2개를 보면 이 문제의 핵심!로직!이 보일 수 있는데 그건 바로 or연산(|)이다.

1. 각 arr1, arr2의 가로줄에 해당하는 값을 하나의 이진수 값으로 두고,
2. 두 값을 OR(|)연산한다. (0101 | 1010 = 1111 //둘 중 하나라도 1인 경우 1로 처리시키도록)
3. 연산한 값이 4자리라고 가정(0001)한다면, 각 자리별 (0, 0, 0, 1)의 값을 확인하여
   3-1. 1(벽)이라면, answer배열의 i위치에 "#"을 더해준다.
   3-2. 0(공백)이라면, answer배열의 i위치에 " "을 더해준다.
   //더해줄 때 string은 append()해준다!

각 자리별 탐색 시 AND(&)연산을 이용하여 해당 위치의 인덱스 값을 반환

(temp & (i << j) ==  temp값과 1 << j (1을 j만큼 shift)한 값과 AND연산하여 인덱스 값 구함
ex. temp ==  10101
     4번째 비트 값 : 10101 & (1 << 3) = 10101 & 01000 → 0
     5번째 비트 값 : 10101 & (1 << 4) = 10101 & 10000 → 10000

주의사항

• 처음 answer 백터를 초기화해주지 않으면 오류가 발생한다.

📌코드

#include <string>
#include <vector>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2)
{
    vector<string> answer(n, ""); //n개 짜리 백터를 ""로 초기화

    for (int i = 0; i < n; i++)
    {
        int bit = arr1[i] | arr2[i]; //row별로 비트 계산
        for (int j = n - 1; j >= 0; j--)
        {
            if (bit & (1 << j))
            { //최하위 비트부터 탐색(1 << j)!! 해당 위치의 인덱스 값 반환
                //append()는 string의 함수
                answer[i].append("#");
            }
            else
            {
                answer[i].append(" ");
            }
        }
    }

    return answer;
} 

회고
이 문제는 친구는 동기랑 같이 코테 문제 풀기 인증 스터디를 하는 중인데, 비트연산으로 풀어보라고 한 것을 추천 받아 다시 풀어보았다.
지난 번에도 비트 연산으로 풀었던 문제이긴 하나 풀이를 알고는 쉽게 접근했지만 풀이를 떠올리기까지 나름 머리를 썼던 문제라 잊을까봐 적어두고 두고두고 봐야지.
비트연산!!!!!공부하자!!!!!!!!!

참고자료