굳건하게

[ 알고리즘풀이 ]

규칙만 찾으면 구현은 간단한 문제입니다.

n = 1 [ 0 ]

n = 2 [ 0 0 1 ]

n = 3 [ 0 0 1 0 0 1 1 ]

n = 4 [ 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 ]

n = 5 [ 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 ]

n = k 일 때, 파란색 부분을 보시면 n = k - 1일 때와 동일한 것을 파악할 수 있습니다. 빨간색 부분도 자세히 보면 n = k - 1 일 때에서 검은색 부분인 '0' 만 '1'로 바꿔주면 나머지 부분은 동일한 것을 확인할 수 있습니다. 따라서, 파란색 부분을 의미하는 left 와 빨간색 부분을 의미하는 right 를 갱신해나가며 답을 구할 수 있습니다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;

    string left = "0", right = "1";
    for(int i = 2; i <= n; i++){
        string ltmp = left + '0', rtmp = left + '1';
        ltmp = ltmp + right; rtmp = rtmp + right;
        left = ltmp; right = rtmp;
    }
    for(int i = 0; i < left.size(); i++){
        answer.push_back(left[i] - '0');
    }

    return answer;
}

[ 알고리즘풀이 ]

■ 우리는 현재 탑에서 지금까지 순회한(왼쪽에 있는 탑들) 탑 중 나보다 높이가 큰 가장 가까운 탑을 고르면 된다.

- 왼쪽부터 순회하며 자료구조 Stack을 이용하면 문제를 간단히 해결할 수 있다.

- 현재 Stack이 비어있다면, 나보다 큰 탑이 없는 걸로 판단하고 answer에 '0', Stack에 현재 탑을 Push.

- Stack이 비어있지않다면, 나보다 큰 탑을 찾을 때까지 Stack을 Pop한다. 나보다 작은 탑들(Pop되는 탑들)은 어차피 나보다 작은 탑이라 앞으로 오른쪽 탑에서 보내는 수신 신호를 받지 못한다.

#include <string>
#include <stack>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    stack<pair<int, int>> s;
    for (int i = 0; i < heights.size(); i++) {
        while (!s.empty()) {
            if (s.top().first <= heights[i]) {
                s.pop();
            }
            else {
                answer.push_back(s.top().second);
                s.push({ heights[i], i + 1 });
                break;
            }
        }
        if (s.empty()) {
            answer.push_back(0);
            s.push({ heights[i], i + 1 });
        }
    }
    return answer;
}

[ 알고리즘풀이 ]

3진법처럼 n을 3으로 나눠가면서 나머지에 따라 값을 answer에 변환되는 수를 쌓고, 반대로 출력해주면 된다.

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

string solution(int n) {
	string answer = "";
	while (n) {
		if (n % 3 == 1)
			answer += '1';
		else if (n % 3 == 2)
			answer += '2';
		else
			answer += '4';
		n--;
		n /= 3;
	}
	reverse(begin(answer), end(answer));
	return answer;
}

[ 알고리즘풀이 ]

 우리는 주어진 skill_trees 중 skill 과 관련된 알파벳만 신경쓰면 되므로, 먼저 skill 을 순회하며 skill 에 나온 Alphabet을 체크한다. 그 후, skill_trees의 tree들을 모두 순회하며, pointer j 를 이용해 tree 중 우리가 신경써야되는 알파벳이 현재 주어진 skill 과 순서가 맞는지 확인하고 아니라면 다음 tree로 넘어간다.

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    bool checkAlphabet[26]={};
    for(int i = 0; i < skill.length(); i++)
        checkAlphabet[skill[i] - 'A'] = 1;
    
    for(int i = 0; i < skill_trees.size(); i++){
        bool check = true;
        int j = 0;
        for(int k = 0; k < skill_trees[i].length(); k++){
            if(!checkAlphabet[skill_trees[i][k] - 'A'])
                continue;
            if(skill[j] != skill_trees[i][k]){
                check = false;
                break;
            }
            j++;
        }
        if(check)
            answer++;
    }
    return answer;
}