쌓고 쌓다
[프로그래머스] 1차 비밀지도 C++ 풀이 본문
https://programmers.co.kr/learn/courses/30/lessons/17681?language=cpp
전체 코드
#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일 것이고 이때 공백을 그려주면 됩니다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 같은 숫자는 싫어 C++ 풀이 (0) | 2022.07.04 |
---|---|
[프로그래머스] 가운데 글자 가져오기 C++ 풀이 (0) | 2022.07.04 |
[프로그래머스] 부족한 금액 계산하기 C++ 풀이 (0) | 2022.07.04 |
[프로그래머스] 나머지가 1이 되는 수 찾기 C++ 풀이 (0) | 2022.07.04 |
[프로그래머스] 최소직사각형 C++ 풀이 (0) | 2022.07.04 |