03.스킬트리

• 문제이해
  
  문제 이름으로 봐서는 트리구조와 관련된 문제같지만 아니였다. 문자열(스킬트리)들 중에서 원하는 조건(문자 순서)를 반드시 만족하는 문자열의 개수를 구하는 문제이다.
  

• pseudo code

  문자열에 하나씩 접근한다.
  접근한 문자열에서 문자를 하나씩 조건과 대조를 한다.
  모든 조건을 만족했을 경우 count의 수를 증가시켜준다.

• 문제점
  처음 문제를 봤을 때 3중 loop를 통해서 문제를 해결하면 되겠다고 생각했다. 그러나 조건에서 문자열의 앞뒤 순서와 꼭 모든 문자열이 있지 않아도 된다는 조건을 적용시키는데 막혔다. 나중에 보니 반복문을 통해서도 문제 해결은 가능했다. 그러나 효율적이고 새로운 방식을 통해 문제를 풀어보고자 map을 공부하고 적용시켜보기로 했다.

• map

  map헤더파일에 존재
  선언은 map<'type1','type2'> 변수명
  type1: key, type2: value로 키와 값으로 구성
  Key의 중복을 허용하지 않는 것이 특징!(중복을 허용하는 multi_map이 존재)
  또한, key값으로 자동으로 정렬해준다. (default는 오름차순)
  내림차순은 map<int, string, greater< int >>
  문자열이 key값일 경우 첫글자를 기준으로 정렬해준다.

  • 저장 형태
    

• 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를 통해 반복문으로 원소에 쉽게 접근할 수 있으니 잘 사용하자!!