쌓고 쌓다

[프로그래머스] 1차 비밀지도 C++ 풀이 본문

알고리즘/프로그래머스

[프로그래머스] 1차 비밀지도 C++ 풀이

승민아 2022. 7. 4. 20:06

https://programmers.co.kr/learn/courses/30/lessons/17681?language=cpp 

 

코딩테스트 연습 - [1차] 비밀지도

비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다

programmers.co.kr

 

전체 코드

#include <string>
#include <vector>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    int k=1;
    for(int i=0;i<n-1;i++)
    {
        k*=2;
    }
    
    for(int i=0;i<n;i++)
    {
        string str;
        for(int j=k;j>0;j/=2)
        {
            bool flag=false;
            
            if(arr1[i]-j>=0)
            {
                str+="#";
                arr1[i]-=j;
                flag=true;
            }
            
            if(arr2[i]-j>=0)
            {
                if(flag==false)
                    str+="#";
                arr2[i]-=j;
                flag=true;
            }
            
            if(flag==false)
                str+=" ";
        }
        answer.push_back(str);
        
    }
    
    return answer;
}

 

 

 

int k=1;
for(int i=0;i<n-1;i++)
{
	k*=2;
}

각 원소 x를 이진수로 변환하기 위해서

k에 n일때 가질 수 있는 한 비트로 가질 수 있는 최대 수를 구합니다.

예로, n이 5일때 '00000' -> 0에 1 또는 0인 이진수를 가질 텐데 맨 앞(첫 비트) "0"0000 에 1이면 16으로

최대 수를 가질 수 있습니다.

그래서 k에 2를 곱하여 n일때 가질 수 있는 최대 수를 찾아 담는 겁니다.

 

for(int i=0;i<n;i++)
{
    string str;
    bool flag=false;
}

arr배열에 n개의 원소 x가 담겨 있을 텐데

이를 차근차근 접근할 것입니다.

str에는 i번째 행의 원래 비밀지도를 해독한 문자열을 만들어줄 겁니다.

flag는 중복해서 #을 넣지 않기 위해, #을 만들어 냈다면 공백(" ")을 넣기 위해 확인을 위해 존재합니다.

 

 

for(int j=k;j>0;j/=2)
{ }

주어진 x를 이진수로 바꿀 때, k를 이용하여 0 또는 1 을 맞춰 나갑니다.

 

if(arr1[i]-j>=0)
{
	str+="#";
	arr1[i]-=j;
	flag=true;
}

만약 주어진 수 x에 j로 뺄 수 있으면 이 자리는 1로 채울 수 있는 것이므로 "#"을 그려주고, x에 j를 뺍니다.

그리고 벽("#")을 세웠으므로 flag를 true로 바꾸어 추후에 중복해서 벽을 세우거나 공백을 그려야 할지 판단합니다.

 

if(arr2[i]-j>=0)
{
	if(flag==false)
	str+="#";
	arr2[i]-=j;
	flag=true;
}

위와 동일하게 구하는데

비트를 1로 해독이 가능할 때, 무작정 벽을 추가해버리면 안 됩니다.

위에서 벽을 그렸는데 또 벽을 그린다면 문제가 되니깐요.

flag가 false일 때만 벽("#")을 그려줍니다.

마찬가지로 추후에 판별을 위해 flag를 true로 바꾸어줍니다.

 

if(flag==false)
	str+=" ";

벽을 한 번이라도 못 그렸다면 flag는 false일 것이고 이때 공백을 그려주면 됩니다.

 

Comments