03.スキルツリー

問題を理解する

問題の名前から見ると、これはツリー構造に関する問題のようですが、そうではありません.文字列(スキルツリー)で必要な条件(文字順)を満たさなければならない文字列の個数を求める問題.

pseudo code
個々のアクセス文字列.アクセスした文字列で、各文字を条件と照合します.すべての条件を満たすとcountの数を増やすことができます.

に質問
初めて問題を見た時に三重loopで解決すればいいと思いましたしかし、条件の下で、適用は必ずしも文字列の前後順序と必ずしもすべての文字列があるとは限らない条件が阻害される.後から見ると、繰り返し文字でも問題が解決します.しかし,効率的な新しい方法で問題を解決するために,地図の学習と応用を決定した.

map
mapヘッダファイルの存在宣言は、map<「type 1」、「type 2」>変数名type 1:key、type 2:valueから構成されます.
キーの繰り返しが許されないのが特徴!(重複を許容するマルチmapが存在する)
また、自動的にキー値がソートされます.(defaultは昇順で並べ替えられます)
降順はmap>
文字列がキー値の場合は、最初のアルファベットでソートします.

ストレージ形式

アプリケーションコードのマッピング

#include <map>
#include <iostream>
#include <string>
using namespace std;

int main() {
	map<int, string> m1;
	map<char, int> m2;
	map<string, int>m3;
    
	//m1 생성법
	//map의 속성
	//키가 되는 값의 중복을 허용하지 않는다. 중복을 허용하는 map을 만들려면 multi_map이라고 따로 있다.
	//map.insert(pait<type,type>)를 통해 입력한다.
	//만약 중복되는 키값의 입력이 있다면 먼저 있던 값이 유지 된다.
	//또한 키값에 자동 정렬된다.
	m1.insert(pair<int, string>(40, "me"));
	m1.insert(pair<int, string>(35, "show"));
	m1.insert(pair<int, string>(10, "Dok2"));
	m1.insert(pair<int, string>(20, "lee"));
	m1.insert(pair<int, string>(10, "kim"));
	
    	//반복문을 통해 접근하여 값을 수정할 수 있다.
	for (int i = 0; i < 3; i++) {
		m1[i] = "auto";
	}

	//접근 방법
	//iterator를 통해 접근하기
	map<int, string> ::iterator iter;

	for (iter = m1.begin(); iter != m1.end(); iter++) {
		cout << "[" << iter->first << "," << iter->second << "]" << "  ";
	}
	cout << endl;
    
	//문자열이 키값일 경우 첫글자를 기준으로 정렬한다.
	m3.insert(pair<string, int>("lee", 1));
	m3.insert(pair<string, int>("kim", 2));
	m3.insert(pair<string, int>("park", 3));
	m3.insert(pair<string, int>("hwang", 4));

	map<string, int> ::iterator iter1;

	for (iter1 = m3.begin(); iter1 != m3.end(); iter1++) {
		cout << "[" << iter1->first << "," << iter1->second << "]" << endl;
	}
	return 0;
}
> 참고:https://hwan-shell.tistory.com/149


- 문제 풀이

#include
#include
#include
using namespace std;
int solution(string skill, vector skill_trees) {
int answer = 0;

map<char,int>skillTree;

//맵생성
for(int i = 0 ; i<skill.size();i++){
    skillTree[skill[i]] = i+1;
}

for(int i = 0 ; i<skill_trees.size();i++){
    
    int count = 1;
    bool check = true;
    
    for(int j = 0 ; j<skill_trees[i].size();j++){
     if(skillTree[skill_trees[i][j]]>count){
        check = false;
         break;
     }
        else if(skillTree[skill_trees[i][j]]==count){
            count++;
        }
    }
  if(check)
      answer++;
}
return answer;

}

- 정리
  map에 대해서 공부하고 사용해보았다. 꽤나 고민했던 부분이 수월하게 해결할 수 있었다.
  특히나 값을 만족하는 인덱스가 필요할 때 잘 활용할 수 있는 것 같다. 
  또한 iterator를 통해 반복문으로 원소에 쉽게 접근할 수 있으니 잘 사용하자!!