[프로그래머스/Level 1] 비밀지도 (C++)

programmers.co.kr/learn/courses/30/lessons/17681

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

 

풀이

10진수의 값을 2진수로 자유롭게 변경할 수 있다면 어렵지 않게 풀 수 있는 문제입니다. 알고리즘은 다음과 같습니다.

 

• 덱을 선언한 후, 10진수의 값을 2로 계속 나눠가며 그 나머지 값을 push_front()를 이용하여 넣어줬습니다.
• 그 후, 2진수로 변환된 수의 길이를 맞추기 위해서 n과 일치할 때까지 0을 push_front() 해줬습니다.
• 예를들어 n=5이고 9를 2진수로 변환해서 덱에 넣으면 1001(2)가 되기 때문에 5자리로 맞추기 위해서 덱의 사이즈가 n과 같아질 때까지 while문을 돌려 push_front()로 0을 넣어줬습니다.
•  마지막으로 두 덱의 요소들을 비교하여 알맞게 '#' 또는 ' '을 문자열에 넣어줍니다.

 

 

전체 코드

#include <string>
#include <vector>
#include <deque>
using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    for(int i=0;i<arr1.size();i++) {
        deque<int> dq1,dq2;
        
        while(arr1[i]!=0) {
            dq1.push_front(arr1[i]%2);
            arr1[i]/=2;
        }
        while(dq1.size()!=n) dq1.push_front(0);
        
        while(arr2[i]!=0) {
            dq2.push_front(arr2[i]%2);
            arr2[i]/=2;
        }
        while(dq2.size()!=n) dq2.push_front(0);
        
        string str="";
        for(int i=0;i<dq1.size();i++) {
            if(dq1[i]==0 && dq2[i]==0) str+=' ';
            else str+='#';
        }
        answer.push_back(str);
    }
    return answer;
}

 

베스트 코드

#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++){
        arr1[i] = arr1[i]|arr2[i];
        string ans = "";
        for(int j = 0; j<n; j++){
            if(arr1[i] % 2 == 0) ans = " " + ans;
            else ans = "#" + ans;
            arr1[i] = arr1[i] >> 1;
        }
        answer.push_back(ans);
    }
    return answer;
}

 

이미 컴퓨터의 모든 값은 0과 1로 이루어진 이진수 형태라는 것을 이용하여 비트 연산을 이용하는 좋은 풀이법도 존재합니다. (상상도 못했음 ㅠ) 더 공부를 열심히 해야겠네요..

 

6개월 뒤 풀이 (bit 연산)

#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 tmp = "";
        for(int j = 0; j < n; j++) {
            // arr1[i]와 arr2[i]를 2진수로 나타내고,
            // 각각의 비트를 비교 둘 중에 하나라도 1이면, (or 연산) "#"을 앞에 추가
            // 만약 둘다 0이라면 " "을 앞에 추가
            if( (arr1[i] & (1 << j)) || (arr2[i] & (1 << j)) ) tmp.insert(0, "#");
            else tmp.insert(0, " ");
        }
        answer.push_back(tmp);
    }
    
    return answer;
}

 

string에 앞에 값을 넣으려면 insert의 첫번째 인자로 이터레이터를 사용안하고 인덱스 번호를 사용하는 것 같음