[프로그래머스] 비밀지도 - LEVEL1

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17681

---

✍️ 문제 풀이

해당 문제는 특별한 부분은 없고, 10진수를 2진수로 변환하는 게 중점인 문제였다. 딴 짓 하면서 뇌를 빼놓고 풀어서 코드가 더럽다.

1) 각 칸에 arr1과 arr2를 2진수로 변환한 값들을 저장하는 N x N 크기의 이차원 벡터 arr1_map과 arr2_map을 선언한다. 그리고 그 둘을 합쳐 '#'과 공백으로 맵을 만들어 저장할 이차원 벡터 result도 선언한다.

2) maxBin에 2^(n-1)을 저장한다.

3) 각 줄에 주어진 수 arr1[i], arr[2]를 maxBin 부터 1까지 점점 작아지는 2의 n승의 수로 나누면서 2진수로 변환해 arr1_map과 arr2_map에 저장한다.

4) arr1_map과 arr2_map에서 한 쪽이라도 1인 칸은 result에서 동일한 인덱스의 칸에 '#'을 넣어준다.

5) string을 저장하는 벡터 answer를 선언하고, result의 한 행씩 묶어 string으로 바꾸고 차례대로 answer에 삽입한 뒤 이를 반환한다.

---

🖥️ 풀이 코드

#include <iostream>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) 
{
    vector<int> set_int(n, 0);
    vector<char> set_char(n, ' ');

    vector<vector<int>> arr1_map(n, set_int);
    vector<vector<int>> arr2_map(n, set_int);
    vector<vector<char>> result(n, set_char);

    int maxBin = (int)pow(2, n - 1);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (j == 0)
            {
                arr1_map[i][j] = arr1[i] / maxBin;
                arr1[i] -= maxBin * (arr1[i] / maxBin);
            }
            else
            {
                arr1_map[i][j] = arr1[i] / (maxBin / (int)pow(2, j));
                arr1[i] -= (maxBin / (int)pow(2, j)) * (arr1[i] / (maxBin / (int)pow(2, j)));
            }
        }

        for (int k = 0; k < n; k++)
        {
            if (k == 0)
            {
                arr2_map[i][k] = arr2[i] / maxBin;
                arr2[i] -= maxBin * (arr2[i] / maxBin);
            }
            else
            {
                arr2_map[i][k] = arr2[i] / (maxBin / (int)pow(2, k));
                arr2[i] -= (maxBin / (int)pow(2, k)) * (arr2[i] / (maxBin / (int)pow(2, k)));
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr1_map[i][j] == 1 || arr2_map[i][j] == 1)
                result[i][j] = '#';
        }
    }

    vector<string> answer;
    for (int i = 0; i < n; i++)
    {
        string str;
        for (int j = 0; j < n; j++)
        {
            str += result[i][j];
        }
        answer.push_back(str);
    }

    return answer;
}

---

❗추가 보충

내가 한 풀이는 가장 기본적인 방법이긴 하지만 너무 난잡한 것 같다고 생각한 와중에, 스터디원의 풀이가 굉장히 간결하고 깔끔한 방법인 것 같아서 복기하는 차원에서 한 번 올려본다.

해당 방법은 비트 연산을 이용한 것으로, arr1과 arr2에 주어지는 수들을 비트 연산을 통해 2진수로 바꾸는 방법이다.

먼저 첫 번째 테스트 케이스의 arr1을 예로 들면,
arr[0] == 9 = 01001(2)

이를 비트연산하면

9 >> 4 = 01001 >> 4 = 00000
9 >> 3 = 01001 >> 3 = 00001
9 >> 2 = 01001 >> 2 = 00010
9 >> 1 = 01001 >> 1 = 00100
9 >> 0 = 01001 >> 0 = 01001

각 자리수에 해당하는 수가 맨 오른쪽으로 옮겨오게 된다. 이를 1(00001)과 비트 AND(&) 하게 되면 해당 자리수가 1인지 아닌지 확인할 수 있다.

ans += ((arr1[i] >> j) & 1) || ((arr2[i] >> j) & 1) == 1 ? "#" : " ";

또한 이 부분은 삼항연산자라고 하며, 조건문 ? 반환값 1 : 반환값 2 와 같은 형식을 가진다.
조건문이 true이면 반환값 1을, false이면 반환값 2를 반환한다.

---

🖥️ 참조 코드

#include <string>
#include <vector>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) 
{
	vector<string> answer;
	for (int i = 0; i < n; i++) {
		string ans = "";
		for (int j = n - 1; j >= 0; j--) {
			ans += ((arr1[i] >> j) & 1) || ((arr2[i] >> j) & 1) == 1 ? "#" : " ";
		}
		answer.push_back(ans);
	}
	return answer;
}